Functional graphs of polynomials and their twist over finite fields

Recently, functional graphs, i.e., graphs generated from a polynomial function over Finite Fields Fp, have received renewed interest, due to their applications in Computer Science. In this thesis, we study new functional graphs of degree two generated by a polynomial and its twist. We perform a computational analyses of these functional graphs by developing new algorithms, and optimizing their implementation performances (including multi-threading). Our results show that (i) most graphs are strongly connected or have only two components (including one giant component and one small component of two or three vertices); (ii) every connected component of the graph have many Hamiltonian cycles (growing exponentially with the finite field); (iii) these Hamiltonian cycles can be used to construct balancing binary sequences. Also the Hamiltonian property makes these graphs distinct to well-known random mappings where the expected cycle length is about √p.These experimental results were used to guide several theoretical analysis and then compared with the relevant mathematical proofs.