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

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?)

  • 1. W. R. Alford, A. Granville and C. Pomerance, `There are infinitely many Carmichael numbers', Annals Math. 140 (1994), 703-722. MR 95k:11114
  • 2. R. C. Baker and G. Harman, `Shifted primes without large prime factors', Acta Arith. 83 (1998), 331-361. MR 99b:11104
  • 3. A. Balog, `The prime $k$-tuplets conjecture on average', Analytic Number Theory, Progress in Mathematics 85, Birkhäuser, Boston, 1990, 47-75. MR 92e:11105
  • 4. L. Blum, M. Blum and M. Shub, `A simple unpredictable pseudorandom number generator', SIAM J. Comp., 15 (1986), 364-383. MR 87k:65007
  • 5. J. J. Brennan and B. Geist, `Analysis of iterated modular exponentiation: The orbit of $x^\alpha \bmod N$', Designs, Codes and Cryptography, 13 (1998), 229-245. MR 99b:11086
  • 6. E. R. Canfield, P. Erdos and C. Pomerance,`On a problem of Oppenheim concerning ``Factorisatio Numerorum''', J. Number Theory, 17 (1983), 1-28. MR 85j:11012
  • 7. T. W. Cusick, `Properties of the $x^2 \bmod N$ pseudorandom number generator', IEEE Trans. Inform. Theory, 41 (1995), 1155-1159. MR 96k:65006
  • 8. T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier, Amsterdam, 1998. MR 99h:94045
  • 9. P. Erdos, C. Pomerance and E. Schmutz, `Carmichael's lambda function', Acta Arith., 58 (1991), 363-385. MR 92g:11093
  • 10. 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. CMP 98:09
  • 11. 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.
  • 12. J. B. Friedlander and I. E. Shparlinski, `On the distribution of the power generator', Math. Comp., (to appear).
  • 13. F. Griffin and I. E. Shparlinski, `On the linear complexity profile of the power generator', Preprint, 1998, 1-11.
  • 14. H. Halberstam and H.-E. Richert, Sieve methods, Academic Press, London 1974. MR 54:12689
  • 15. 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.
  • 16. A. Hildebrand and G. Tenenbaum, `Integers without large prime factors', J. de Théorie des Nombres de Bordeaux, 5 (1993), 411-484. MR 95d:11116
  • 17. J. C. Lagarias, `Pseudorandom number generators in cryptography and number theory', Proc. Symp. in Appl. Math., Amer. Math. Soc., Providence, RI, 42 (1990), 115-143. MR 92f:11109
  • 18. U. M. Maurer, `Fast generation of prime numbers and secure public-key cryptographic parameters', J. Cryptology, 8 (1995), 123-155. MR 96i:94021
  • 19. A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, FL, 1997. MR 99g:94015
  • 20. C. Pomerance, `On the distribution of amicable numbers', J. Reine Angew. Math., 293/294 (1977), 217-222. MR 56:5402
  • 21. K. Prachar, Primzahlverteilung, Springer-Verlag, Berlin, 1957. MR 19:393b
  • 22. R. L. Rivest, `Remarks on a proposed cryptanalytic attack on the M.I.T. public-key cryptosystem', Cryptologia, 2 (1978), 62-65.
  • 23. R. L. Rivest, A. Shamir and D. A. Wagner, `Time-lock puzzles and timed-release crypto', Preprint, 1996, 1-9.
  • 24. R. L. Rivest and R. D. Silverman, `Are ``strong'' primes needed for RSA?', Preprint, 1999, 1-23.
  • 25. I. E. Shparlinski, `On the linear complexity of the power generator', Designs, Codes and Cryptography, (to appear).
  • 26. D. R. Stinson, Cryptography: Theory and Practice, CRC Press, Boca Raton, FL, 1995. MR 96k:94015

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

American Mathematical Society