Connected components of the graph generated by power maps in prime finite fields

2017/03/27 by Pomerance, Carl, Shparlinski, Igor E.
#FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1703.09292

Abstract

Consider the power pseudorandom-number generator in a finite field \mathbb F_q. That is, for some integer e≥2, one considers the sequence u,u^e,u^e2,… in \mathbb F_q for a given seed u∈ \mathbb F_q^×. This sequence is eventually periodic. One can consider the number of cycles that exist as the seed u varies over \mathbb F_q^×. This is the same as the number of cycles in the functional graph of the map x↦ x^e in \mathbb F_q^×. We prove some estimates for the maximal and average number of cycles in the case of prime finite fields.

Related

• Power maps in finite groups
• Periodic Structure of the Exponential Pseudorandom Number Generator
• Short Cycles in Repeated Exponentiation Modulo a Prime
• Dynamics of polynomial maps over finite fields
• Powers of Hamilton cycles in pseudorandom graphs