Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

Period of the power generator and small values of Carmichael’s functionHTML articles powered by AMS MathViewer

by John B. Friedlander, Carl Pomerance and Igor E. Shparlinski
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
Similar Articles
• 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.