[theory students] theory talk Thursday 8/1 2 PM

[Eric Bach <bach@xxxxxxxxxxx>]

I'd like to give the following presentation
Thursday August 1, 2 PM, in 3310:

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

Analysis and Comparison of Two Algorithms
for Predicting Linear Congruence Generators.
Eric Bach, University of Wisconsin.

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.

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

This is preparation and testing for a 20 minute talk I will give
at the upcoming AMS Sectional Meeting (at UW) in mid-September.

Let me know if for some reason this is not a convenient time.

Eric