When we iterate functions over finite structures, there is an underlying natural functional graph. For a function $f$ over a finite field $\mathbb{F}_q$, this graph has $q$ nodes and a directed edge from vertex $a$ to vertex $b$ if and only if $f(a)=b$. It is well known, combinatorially, that functional graphs are sets of connected components, components are directed cycles of nodes, and each of these nodes is the root of a directed tree from leaves to its root.
The study of iterations of functions over a finite field and their corresponding functional graphs is a growing area of research, in part due to their applications in cryptography and integer factorization methods like Pollard rho algorithm. Periodicity and permutational properties of the function can be explained by its functional graph.
Some functions over finite fields when iterated present strong symmetry properties. These symmetries allow mathematical proofs for some dynamical properties such as period and preperiod of a generic element, (average) ``rho length'' (number of iterations until we cycle back), number of connected components, cycle lengths, etc.
We survey the main problems addressed so far and some of the recent results in this area. We comment on some cryptographical applications and heuristics where one treats functions as random mappings.
As a concrete example, we completely describe the functional graph of Chebyshev polynomials over a finite field. Then, we use our structural results to obtain estimates for the average rho length, average number of connected components and the expected value for the period and preperiod of iterating Chebyshev polynomials.
Based on joint works with Rodrigo S.V. Martins (UTFPR) and Claudio Qureshi (Carleton and Unicamp).
References:
[1] On the heuristic of approximating polynomials over finite
fields by random mappings, R. Martins and D. Panario,
International Journal of Number Theory, 12, 1987-2016, 2016.
[2] Redei actions on finite fields and multiplication map
in cyclic groups, C. Qureshi and D. Panario,
SIAM Journal on Discrete Mathematics, 29, 1486-1503, 2015.
[3] Cycle structure of iterating Redei functions,
C. Qureshi, D. Panario and R. Martins,
Advances in Mathematics of Communications, 11, 397-407, 2017.
[4] The graph structure of the Chebyshev polynomial over
finite fields and applications, C. Qureshi and D. Panario,
in WCC (Workshop on Coding and Cryptography) 2017.<br>
Refe
