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 |