Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Authors: John B. Friedlander, Carl Pomerance and Igor E. Shparlinski
Journal: Math. Comp. 70 (2001), 1591-1605
MSC (2000): Primary 11B50, 11N56, 11T71; Secondary 11Y55, 94A60
Published electronically: July 13, 2000
Corrigendum: Math. Comp. 71 (2002), 1803-1806.
MathSciNet review: 1836921
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


Consider the pseudorandom number generator \begin{equation*}u_n\equiv u_{n-1}^e\pmod{m},\quad 0\le u_n\le m-1,\quad n=1,2,\ldots, \end{equation*}where we are given the modulus $m$, the initial value $u_0=\vartheta$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 $(u_n)$ exceeds $m^{3/4+\varepsilon}$, 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 $\vartheta,e$, the period of the power generator exceeds $(pl)^{1-\varepsilon}$. 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 $\lambda(m)$, the size of the largest cyclic subgroup of the multiplicative group of residues modulo $m$. In particular, we show that for any $\Delta\ge(\log\log N)^3$, we have $\lambda(m)\ge N\exp(-\Delta)$for all integers $m$ with $1\le m\le N$, apart from at most $N\exp\left(-0.69\left(\Delta\log \Delta\right)^{1/3}\right)$ exceptions.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11B50, 11N56, 11T71, 11Y55, 94A60

Retrieve articles in all journals with MSC (2000): 11B50, 11N56, 11T71, 11Y55, 94A60

Additional Information

John B. Friedlander
Affiliation: Department of Mathematics, University of Toronto, Toronto, Ontario M5S 3G3, Canada

Carl Pomerance
Affiliation: Department of Fundamental Mathematics, Bell Labs, Murray Hill, New Jersey 07974-0636

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia

Keywords: Carmichael's function, RSA generator, Blum--Blum--Shub generator
Received by editor(s): September 8, 1999
Published electronically: July 13, 2000
Additional Notes: The first author was supported in part by NSERC grant A5123 and by an NEC grant to the Institute for Advanced Study.
The third author was supported in part by ARC grant A69700294.
Article copyright: © Copyright 2000 American Mathematical Society