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

DOI10.1142/S1793042116501219MaRDI QIDQ2828372zbMATH OpenOpenAlexFDO

Authors Rodrigo S. V. Martins, Daniel Panario

Publication date 25 October 2016

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

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

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)

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.

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

Cites work

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

Cited in

(6)

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

Describes a project that uses

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)