Affordable Access

Short Cycles in Repeated Exponentiation Modulo a Prime

Authors
  • Glebsky, Lev
  • Shparlinski, Igor E.
Type
Preprint
Publication Date
Aug 27, 2009
Submission Date
Aug 27, 2009
Identifiers
arXiv ID: 0908.3920
Source
arXiv
License
Yellow
External links

Abstract

Given a prime $p$, we consider the dynamical system generated by repeated exponentiations modulo $p$, that is, by the map $u \mapsto f_g(u)$, where $f_g(u) \equiv g^u \pmod p$ and $0 \le f_g(u) \le 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.

Report this publication

Statistics

Seen <100 times