Period of the power generator and small values of Carmichael's function

John B. Friedlander*, Carl Pomerance, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

40 Citations (Scopus)

Abstract

Consider the pseudorandom number generator un ≡ ue n-1 (mod m), 0 ≤ un ≤ m - 1, n = 1, 2, . . . , where we are given the modulus m, the initial value u0 = θ and the exponent e. One case of particular interest is when the modulus m is of the form pl, where p, l are different primes of the same magnitude. It is known from work of the first and third authors that for moduli m = pl, if the period of the sequence (un) exceeds m3/4+ε, then the sequence is uniformly distributed. We show rigorously that for almost all choices of p, l it is the case that for almost all choices of θ, e, the period of the power generator exceeds (pl)1-ε. And so, in this case, the power generator is uniformly distributed. We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto. The principal tool is an estimate related to the Carmichael function λ(m), the size of the largest cyclic subgroup of the multiplicative group of residues modulo m. In particular, we show that for any Δ ≥ (log log N)3, we have λ(m) ≥ N exp(-Δ) for all integers m with 1 ≤ m ≤ N, apart from at most N exp (-0.69 (Δ log Δ)1/3) exceptions.

Original languageEnglish
Pages (from-to)1591-1605
Number of pages15
JournalMathematics of Computation
Volume70
Issue number236
DOIs
Publication statusPublished - Oct 2001

Bibliographical note

Corrigendum can be found in Mathematics of Computation, 71(240), pp. 1803-1806, 2002.
https://doi.org/10.1090/S0025-5718-02-01519-3

Fingerprint

Dive into the research topics of 'Period of the power generator and small values of Carmichael's function'. Together they form a unique fingerprint.

Cite this