Short cycles in repeated exponentiation modulo a prime Article uri icon

abstract

  • Given a prime p, we consider the dynamical system generated by repeated exponentiations modulo p, that is, by the map u → fg(u), where f g (u) ≡ 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. © 2009 Springer Science%2bBusiness Media, LLC.

publication date

  • 2010-01-01