Period of the power generator and small values of Carmichael's function
type: Item
instance of: scholarly article
zbMATH Open document ID: 1029.11043
DOI: 10.1090/S0025-5718-00-01282-5
published in: Mathematics of Computation
publication date: 2001-07-05T00:00:00Z
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 11B50
Mathematics Subject Classification ID: 11N56
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1614801
zbMATH Keywords: Carmichael's function
zbMATH Keywords: RSA generator
zbMATH Keywords: Blum-Blum-Shub generator
Wikidata QID: Q56475224
author: J. B. Friedlander
author: Carl Pomerance
author: Igor E. Shparlinski
MaRDI profile type: Publication
cites work: There are infinitely many Carmichael numbers
cites work: Shifted primes without large prime factors
cites work: Q5750962
cites work: A Simple Unpredictable Pseudo-Random Number Generator
cites work: Analysis of iterated modular exponentiation: The orbits of \(x^\alpha \mod N\)
cites work: On a problem of Oppenheim concerning ''Factorisatio Numerorum''
cites work: Properties of the x/sup 2/ mod N pseudorandom number generator
cites work: Q4208589
cites work: Carmichael's lambda function
cites work: Stronger security proofs for RSA and Rabin bits.
cites work: Q4330627
cites work: On the distribution of the power generator
cites work: Q4052222
cites work: Integers without large prime factors
cites work: Q3974094
cites work: Fast generation of prime numbers and secure public-key cryptographic parameters.
cites work: Q4718481
cites work: On the distribution of amicable numbers.
cites work: Q3248054
cites work: On the linear complexity of the power generator
cites work: Q4839149
title: Period of the power generator and small values of Carmichael's function
review text: The paper considers the pseudorandom number generator NEWLINE\[NEWLINEu_n= u_{n-1}^e\pmod m, \quad 0\leq u_n\leq m-1,\;n=1,2,\dots,NEWLINE\]NEWLINE where the modulus \(m\), the initial state \(u_0=v\) and the exponent \(e\) are given. One particularly interesting case is when the modulus is of the form \(m=pl\) where \(p\) and \(l\) are different primes of the same magnitude. The authors show that for almost all choices of \(p\), \(l\) it holds for almost all choices of \(v\), \(e\) that the period of the generator exceeds \((pl)^{1-\varepsilon}\). From earlier work by some of the authors it follows that this implies that the power generator is uniformly distributed. NEWLINENEWLINENEWLINEOne application of the results are a rigorous proof that the cycling attack on the RSA cryptosystem has a negligible chance to be efficient. NEWLINENEWLINENEWLINEIn the Corrigendum a corrected proof of Theorem 8 is given.
reviewed by: Tor Helleseth
description: scientific article; zbMATH DE number 1614801