[theory students] German Tanks and Zombie Primes

[Eric Bach <bach@xxxxxxxxxxx>]

Come to my talk today to find out what the subject line means!
Eric

PS. to Somesh: Can you forward to the mailing list for people
interested in security (if there is one)?

========================================================

Analysis and Comparison of Two Algorithms
for Predicting Linear Congruence Generators.
Eric Bach
2 PM 8/1/19
3310 CS

Pseudo-random numbers have long been made by iterating
an affine map f(x) = ax+b on Z/n.  Motivated
by cryptanalysis, Reeds in 1977 and Boyar (Plumstead) in 1982
published methods to infer the generator from observations.
The first uses determinants and initially obtains n via factorization, and the
second avoids factorization and initially computes a using an iterated gcd
process.

For some examples, Reeds's method fails, making Boyar's superior on unlimited
data.  With a fixed number of
observations, however, each can handle cases the other cannot.

We also consider the expected length of Boyar's gcd
process.  After replacing Z/n by the Prufer ring (the direct product of all
p-adic integer rings), we model
Boyar's sample differences by independent draws from this
ring. We then express the expectation using Euler products.
This matches the observed mean length when n is a product of large primes.  When
n is a high power of the prime l (practitioners use l=2), the p=l factor should
be omitted from the Euler products.  Other cases, such as n twice a prime,
require more intricate modifications to local factors.