Short cycles in repeated exponentiation modulo a prime

作者：Glebsky Lev; Shparlinski Igor E^*

来源：Designs, Codes and Cryptography, 2010, 56(1): 35-42.

DOI：10.1007/s10623-009-9339-2

• Discrete logarithm
• Cycle
• Dynamical system

Given a prime p, we consider the dynamical system generated by repeated exponentiations modulo p, that is, by the map u bar right arrow f(g)(u), where f(g)(u) equivalent to g(u) (mod p) and 0 <= f(g) (u) <= p - 1. This map is in particular used in a number of constructions of cryptographically secure pseudorandom generators. We obtain nontrivial upper bounds on the number of fixed points and short cycles in the above dynamical system.

• 出版日期2010-7