Functional graphs of polynomials over finite fields

Sergei V. Konyagin, Florian Luca, Bernard Mans, Luke Mathieson, Min Sha, Igor E. Shparlinski

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

Given a function f in a finite field Fq of q elements, we define the functional graph of f as a directed graph on q nodes labelled by the elements of Fq where there is an edge from u to v if and only if f(u)=v. We obtain some theoretical estimates on the number of non-isomorphic graphs generated by all polynomials of a given degree. We then develop a simple and practical algorithm to test the isomorphism of quadratic polynomials that has linear memory and time complexities. Furthermore, we extend this isomorphism testing algorithm to the general case of functional graphs, and prove that, while its time complexity deviates from linear by a (usually small) multiplier dependent on graph parameters, its memory complexity remains linear. We exploit this algorithm to provide an upper bound on the number of functional graphs corresponding to polynomials of degree d over Fq. Finally, we present some numerical results and compare function graphs of quadratic polynomials with those generated by random maps and pose interesting new problems.

Original languageEnglish
Pages (from-to)87-122
Number of pages36
JournalJournal of Combinatorial Theory. Series B
Volume116
DOIs
Publication statusPublished - Jan 2016

Keywords

  • Polynomial maps
  • Functional graphs
  • Finite fields
  • Character sums
  • Algorithms on trees

Fingerprint Dive into the research topics of 'Functional graphs of polynomials over finite fields'. Together they form a unique fingerprint.

  • Cite this