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

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 [Enhancements On Off] (What's this?)

  • 1. 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, 10.2307/2118576
  • 2. R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361. MR 1610553
  • 3. Antal Balog, The prime 𝑘-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, 10.1007/978-1-4612-3464-7_5
  • 4. L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364–383. MR 837589, 10.1137/0215025
  • 5. J. J. Brennan and Bruce Geist, Analysis of iterated modular exponentiation: the orbits of 𝑥^{𝛼}\bmod𝑁, Des. Codes Cryptogr. 13 (1998), no. 3, 229–245. MR 1601580, 10.1023/A:1008289605486
  • 6. 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, 10.1016/0022-314X(83)90002-1
  • 7. Thomas W. Cusick, Properties of the 𝑥² mod 𝑁 pseudorandom number generator, IEEE Trans. Inform. Theory 41 (1995), no. 4, 1155–1159. MR 1366760, 10.1109/18.391261
  • 8. 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
  • 9. Paul Erdős, Carl Pomerance, and Eric Schmutz, Carmichael’s lambda function, Acta Arith. 58 (1991), no. 4, 363–385. MR 1121092
  • 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 [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. London Mathematical Society Monographs, No. 4. MR 0424730
  • 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. Adolf Hildebrand and Gérald Tenenbaum, Integers without large prime factors, J. Théor. Nombres Bordeaux 5 (1993), no. 2, 411–484. MR 1265913
  • 17. 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, 10.1090/psapm/042/1095554
  • 18. Ueli M. Maurer, Fast generation of prime numbers and secure public-key cryptographic parameters, J. Cryptology 8 (1995), no. 3, 123–155. MR 1346019, 10.1007/BF00202269
  • 19. 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
  • 20. Carl Pomerance, On the distribution of amicable numbers, J. Reine Angew. Math. 293/294 (1977), 217–222. MR 0447087
  • 21. Karl Prachar, Primzahlverteilung, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 0087685
  • 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. Douglas R. Stinson, Cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1995. Theory and practice. MR 1327060

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
Email: frdlndr@math.toronto.edu

Carl Pomerance
Affiliation: Department of Fundamental Mathematics, Bell Labs, Murray Hill, New Jersey 07974-0636
Email: carlp@research.bell-labs.com

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
Email: igor@ics.mq.edu.au

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01282-5
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