On the heuristic of approximating polynomials over finite fields by random mappings

DOI10.1142/S1793042116501219zbMATH Open1382.12004arXiv1505.02983OpenAlexW3098915281MaRDI QIDQ2828372FDOQ2828372

Authors: Rodrigo S. V. Martins, Daniel Panario 

Publication date: 25 October 2016

Published in: International Journal of Number Theory (Search for Journal in Brave)

Abstract: The study of iterations of functions over a finite field and the corresponding functional graphs is a growing area of research with connections to cryptography. The behaviour of such iterations is frequently approximated by what is know as the Brent-Pollard heuristic, where one treats functions as random mappings. We aim at understanding this heuristic and focus on the expected rho length of a node of the functional graph of a polynomial over a finite field. Since the distribution of indegrees (preimage sizes) of a class of functions appears to play a central role in its average rho length, we survey the known results for polynomials over finite fields giving new proofs and improving one of the cases for quartic polynomials. We discuss the effectiveness of the heuristic for many classes of polynomials by comparing our experimental results with the known estimates for random mapping models defined by different restrictions on their distribution of indegrees. We prove that the distribution of indegrees of general polynomials and mappings have similar asymptotic properties, including the same asymptotic average coalescence. The combination of these results and our experiments suggests that these polynomials behave like random mappings, extending a heuristic that was known only for degree $2$. We show numerically that the behaviour of Chebyshev polynomials of degree $dgeq2$ over finite fields present a sharp contrast when compared to other polynomials in their respective classes.

Full work available at URL: https://arxiv.org/abs/1505.02983

Recommendations

• Periods of iterations of mappings over finite fields with restricted preimage sizes
• Periods of iterations of functions with restricted preimage sizes
• A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields
• A survey on iterations of mappings over finite fields
• The graph structure of Chebyshev polynomials over finite fields and applications

zbMATH Keywords

value set of polynomialsdynamical systems over finite fieldsgeneral polynomialsBrent-Pollard heuristic

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Arithmetic and non-Archimedean dynamical systems involving polynomial and rational maps (37P05)

Cites Work

• Analytic combinatorics
• Handbook of finite fields
• The arithmetic of dynamical systems
• Monte Carlo Methods for Index Computation (mod p)
• Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Elliptic and hyperelliptic curves: a practical security analysis
• The distribution of the residues of a quartic polynomial
• The distribution of polynomials over finite fields
• A monte carlo method for factorization
• Title not available (Why is that?)
• Title not available (Why is that?)
• On random walks for Pollard's rho method
• A new criterion for permutation polynomials
• On the cycle structure of repeated exponentiation modulo a prime
• An improved Monte Carlo factorization algorithm
• Title not available (Why is that?)
• On the correct use of the negation map in the Pollard rho method
• On the use of the negation map in the Pollard rho method
• Note on a problem of Chowla
• Random mappings with restricted preimages
• Sur le nombre des valeurs distinctes d'un polynôme à coefficients dans un corps fini
• Functional graphs of polynomials over finite fields
• Title not available (Why is that?)

Cited In (6)

• On functional graphs of quadratic polynomials
• Iteration entropy
• Periods of iterations of mappings over finite fields with restricted preimage sizes
• A limit theorem for the six-length of random functional graphs with a fixed degree sequence
• Periods of iterated rational functions
• Erratum: ``On the heuristic of approximating polynomials over finite fields by random mappings

Uses Software

• ECPP

This page was built for publication: On the heuristic of approximating polynomials over finite fields by random mappings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828372)