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

Abstract: Consider the power pseudorandom-number generator in a finite field

{m a t h b b F}_{q}

. That is, for some integer

e g e 2

, one considers the sequence

u, u^{e}, u^{e^{2}}, d o t s

in

{m a t h b b F}_{q}

for a given seed

u i n {m a t h b b F}_{q}^{i} m e s

. This sequence is eventually periodic. One can consider the number of cycles that exist as the seed

u

varies over

{m a t h b b F}_{q}^{i} m e s

. This is the same as the number of cycles in the functional graph of the map

x m a p s t o x^{e}

in

{m a t h b b F}_{q}^{i} m e s

. We prove some estimates for the maximal and average number of cycles in the case of prime finite fields.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Connected components of the graph generated by power maps in prime finite fields