Macquarie University
01whole.pdf (498.01 kB)

Functional graphs of polynomials and their twist over finite fields

Download (498.01 kB)
posted on 2022-03-28, 20:13 authored by Jeffrey Smith
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.


Table of Contents

1. Introduction -- 2. Building experimentation tools -- 3. Connected graph analysis -- 4. Hamiltonian cycle analysis -- 5. Discussion -- 6. Conclusion.


Bibliography: pages 43-44 Empirical thesis.

Awarding Institution

Macquarie University

Degree Type

Thesis MRes


MRes, Macquarie University, Faculty of Science and Engineering, Department of Computing

Department, Centre or School

Department of Computing

Year of Award


Principal Supervisor

Bernard Mans


Copyright Jeffrey Smith 2019. Copyright disclaimer:




1 online resource (44 pages) graphs, tables

Former Identifiers