01whole.pdf (498.01 kB)
Download file

Functional graphs of polynomials and their twist over finite fields

Download (498.01 kB)
thesis
posted on 28.03.2022, 20:13 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.

History

Table of Contents

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

Notes

Bibliography: pages 43-44 Empirical thesis.

Awarding Institution

Macquarie University

Degree Type

Thesis MRes

Degree

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

Department, Centre or School

Department of Computing

Year of Award

2019

Principal Supervisor

Bernard Mans

Rights

Copyright Jeffrey Smith 2019. Copyright disclaimer: http://mq.edu.au/library/copyright

Language

English

Extent

1 online resource (44 pages) graphs, tables

Former Identifiers

mq:71067 http://hdl.handle.net/1959.14/1270521