Analysis of Iterated Modular Exponentiation: The Orbits of cursive Greek chiα mod N

Let N and α be integers larger than 1. Define an orbit to be the collection of residues in Z*N generated by iteratively applying x → xα mod N to an element x ∈ Z*N which eventually maps back to itself. An orbit's length is the number of distinct residues in the orbit. When N is a large bicomposite integer, such as is commonly used in many cryptographic applications, and when certain prime factorizations related to N are known, all orbit lengths and the number of orbits of each possible length can be efficiently computed using the results presented. If the required integer factorizations are only partially known, the risk that a randomly selected periodic element might produce an orbit shorter than some (typically large) divisor of φ(φ(N)) can be bounded. The information needed to produce such a bound is fully available when the prime factors of N are generated using the prime generation algorithm defined in Maurer [7]. Results presented can assist in choosing wisely a modulus N for the Blum, Blum, and Shub pseudo-random bit generator. If N is a bicomposite RSA modulus, the analysis shows how to quantify the risk posed by an iterated encryption attack.