## Period of the power generator and small values of Carmichael’s function

HTML articles powered by AMS MathViewer

- by John B. Friedlander, Carl Pomerance and Igor E. Shparlinski PDF
- Math. Comp.
**70**(2001), 1591-1605 Request permission

Corrigendum: Math. Comp.

**71**(2002), 1803-1806.

## Abstract:

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

- W. R. Alford, Andrew Granville, and Carl Pomerance,
*There are infinitely many Carmichael numbers*, Ann. of Math. (2)**139**(1994), no. 3, 703–722. MR**1283874**, DOI 10.2307/2118576 - R. C. Baker and G. Harman,
*Shifted primes without large prime factors*, Acta Arith.**83**(1998), no. 4, 331–361. MR**1610553**, DOI 10.4064/aa-83-4-331-361 - Antal Balog,
*The prime $k$-tuplets conjecture on average*, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 47–75. MR**1084173**, DOI 10.1007/978-1-4612-3464-7_{5} - L. Blum, M. Blum, and M. Shub,
*A simple unpredictable pseudorandom number generator*, SIAM J. Comput.**15**(1986), no. 2, 364–383. MR**837589**, DOI 10.1137/0215025 - J. J. Brennan and Bruce Geist,
*Analysis of iterated modular exponentiation: the orbits of $x^\alpha \bmod N$*, Des. Codes Cryptogr.**13**(1998), no. 3, 229–245. MR**1601580**, DOI 10.1023/A:1008289605486 - E. R. Canfield, Paul Erdős, and Carl Pomerance,
*On a problem of Oppenheim concerning “factorisatio numerorum”*, J. Number Theory**17**(1983), no. 1, 1–28. MR**712964**, DOI 10.1016/0022-314X(83)90002-1 - Thomas W. Cusick,
*Properties of the $x^2$ mod $N$ pseudorandom number generator*, IEEE Trans. Inform. Theory**41**(1995), no. 4, 1155–1159. MR**1366760**, DOI 10.1109/18.391261 - Thomas W. Cusick, Cunsheng Ding, and Ari Renvall,
*Stream ciphers and number theory*, North-Holland Mathematical Library, vol. 55, North-Holland Publishing Co., Amsterdam, 1998. MR**1634586** - Paul Erdős, Carl Pomerance, and Eric Schmutz,
*Carmichael’s lambda function*, Acta Arith.**58**(1991), no. 4, 363–385. MR**1121092**, DOI 10.4064/aa-58-4-363-385 - R. Fischlin and C. P. Schnorr, ‘Stronger security proofs for RSA and Rabin bits’,
*Lect. Notes in Comp. Sci.*, Springer-Verlag, Berlin,**1233**(1997), 267–279. - J. B. Friedlander, D. Lieman and I. E. Shparlinski, ‘On the distribution of the RSA generator’,
*Proc. Intern. Conf. on Sequences and their Applications (SETA’98), Singapore*, Springer-Verlag, London, 1999, 205–212. - J. B. Friedlander and I. E. Shparlinski, ‘On the distribution of the power generator’,
*Math. Comp.*, (to appear). - F. Griffin and I. E. Shparlinski, ‘On the linear complexity profile of the power generator’,
*Preprint*, 1998, 1–11. - H. Halberstam and H.-E. Richert,
*Sieve methods*, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. MR**0424730** - J. Håstad and M. Näslund, ‘The security of individual RSA bits’,
*Proc. 39th IEEE Symp. on Foundations of Comp. Sci.*, 1998, 510–519. - Adolf Hildebrand and Gérald Tenenbaum,
*Integers without large prime factors*, J. Théor. Nombres Bordeaux**5**(1993), no. 2, 411–484. MR**1265913**, DOI 10.5802/jtnb.101 - J. C. Lagarias,
*Pseudorandom number generators in cryptography and number theory*, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 115–143. MR**1095554**, DOI 10.1090/psapm/042/1095554 - Ueli M. Maurer,
*Fast generation of prime numbers and secure public-key cryptographic parameters*, J. Cryptology**8**(1995), no. 3, 123–155. MR**1346019**, DOI 10.1007/BF00202269 - Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone,
*Handbook of applied cryptography*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR**1412797** - Carl Pomerance,
*On the distribution of amicable numbers*, J. Reine Angew. Math.**293(294)**(1977), 217–222. MR**447087**, DOI 10.1515/crll.1977.293-294.217 - Saunders MacLane and O. F. G. Schilling,
*Infinite number fields with Noether ideal theories*, Amer. J. Math.**61**(1939), 771–782. MR**19**, DOI 10.2307/2371335 - R. L. Rivest, ‘Remarks on a proposed cryptanalytic attack on the M.I.T. public-key cryptosystem’,
*Cryptologia*,**2**(1978), 62–65. - R. L. Rivest, A. Shamir and D. A. Wagner, ‘Time-lock puzzles and timed-release crypto’,
*Preprint*, 1996, 1–9. - R. L. Rivest and R. D. Silverman, ‘Are “strong” primes needed for RSA?’,
*Preprint*, 1999, 1–23. - I. E. Shparlinski, ‘On the linear complexity of the power generator’,
*Designs, Codes and Cryptography*, (to appear). - Douglas R. Stinson,
*Cryptography*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1995. Theory and practice. MR**1327060**

## Additional Information

**John B. Friedlander**- Affiliation: Department of Mathematics, University of Toronto, Toronto, Ontario M5S 3G3, Canada
- Email: frdlndr@math.toronto.edu
**Carl Pomerance**- Affiliation: Department of Fundamental Mathematics, Bell Labs, Murray Hill, New Jersey 07974-0636
- MR Author ID: 140915
- Email: carlp@research.bell-labs.com
**Igor E. Shparlinski**- Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
- MR Author ID: 192194
- Email: igor@ics.mq.edu.au
- 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. - © Copyright 2000 American Mathematical Society
- Journal: Math. Comp.
**70**(2001), 1591-1605 - MSC (2000): Primary 11B50, 11N56, 11T71; Secondary 11Y55, 94A60
- DOI: https://doi.org/10.1090/S0025-5718-00-01282-5
- MathSciNet review: 1836921