Skip to main content

On the period of some pseudo-random number generators and "number-theoretical turbulence"

Posted in
Speaker: 
Par Kurlberg
Date: 
Wed, 2013-11-20 11:15 - 12:15
Location: 
MPIM Lecture Hall

Given coprime integers b and n, let ord(b,n) be the
multiplicative order of b modulo n.  The length of the periods of some
popular pseudorandom number generators (e.g., the linear congruential
generator, and the Blum-Blum-Shub generator) turns out to be related
to ord(b,n) for appropriately chosen b and n.  We will investigate
some conclusions by V.I. Arnold (based on numerics by F. Aicardy as
well as analogies with the physical principle of turbulence) on the
average of ord(b,n), as n ranges over integers.  We will also give
lower bounds on ord(b,n) for b fixed and n ranging over certain
subsets of the integers, e.g., the set of primes, the set of "RSA
moduli" (i.e., products of two primes), the full set of integers, and
the images of these sets under the Carmichael lambda function.  (The
lower bounds in the case of RSA moduli shows that certain "cycling
attacks" on the RSA crypto system are ineffective.)  Time permitting
we will discuss similar questions regarding exponents of elliptic
curves mod p, and p varying.

© MPI f. Mathematik, Bonn Impressum & Datenschutz
-A A +A