## Abstract

Consider the pseudorandom number generator u_{n} ≡ u^{e} _{n-1} (mod m), 0 ≤ u_{n} ≤ m - 1, n = 1, 2, . . . , where we are given the modulus m, the initial value u_{0} = θ 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+ε}, 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 θ, e, the period of the power generator exceeds (pl)^{1-ε}. 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 λ(m), the size of the largest cyclic subgroup of the multiplicative group of residues modulo m. In particular, we show that for any Δ ≥ (log log N)^{3}, we have λ(m) ≥ N exp(-Δ) for all integers m with 1 ≤ m ≤ N, apart from at most N exp (-0.69 (Δ log Δ)^{1/3}) exceptions.

Original language | English |
---|---|

Pages (from-to) | 1591-1605 |

Number of pages | 15 |

Journal | Mathematics of Computation |

Volume | 70 |

Issue number | 236 |

DOIs | |

Publication status | Published - Oct 2001 |

### Bibliographical note

Corrigendum can be found in Mathematics of Computation, 71(240), pp. 1803-1806, 2002.https://doi.org/10.1090/S0025-5718-02-01519-3