On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic

DOI10.1137/18M1177196MaRDI QIDQ5382575zbMATH OpenWikidataFDO

Authors Giacomo Micheli

Publication date 18 June 2019

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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

zbMATH Keywords

cryptographyfinite fieldsGalois theoryirreducible polynomialsglobal function fieldsDLP

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Abstract: In this paper we characterize the set of polynomials $finmathbb{F}_q[X]$ satisfying the following property: there exists a positive integer $d$ such that for any positive integer $ell$ less or equal than the degree of $f$, there exists $t_0$ in $mathbb{F}_{q^d}$ such that the polynomial $f-t_0$ has an irreducible factor of degree $ell$ over $mathbb{F}_{q^d}[X]$. This result is then used to progress in the last step which is needed to remove the heuristic from one of the quasi-polynomial time algorithms for discrete logarithm problems (DLP) in small characteristic. Our characterization allows a construction of polynomials satisfying the wanted property. The method is general and can be used to tackle similar problems which involve factorization patterns of polynomials over finite fields.

Recommendations

• Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms
• scientific article; zbMATH DE number 1273636
• Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
• A classification of algorithms for multiplying polynomials of small degree over finite fields
• On polynomial selection for the general number field sieve
• scientific article; zbMATH DE number 177888
• Subquadratic-time factoring of polynomials over finite fields
• scientific article; zbMATH DE number 1263216
• A new efficient factorization algorithm for polynomials over small finite fields

Cites work

• scientific article; zbMATH DE number 798855 (Why is no real title available?)
• scientific article; zbMATH DE number 800817 (Why is no real title available?)
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• A new index calculus algorithm with complexity \(L(1/4+o(1))\) in small characteristic
• A short proof of a Chebotarev density theorem for function fields
• Algebraic Function Fields and Codes
• Exceptional Covers and Bijections on Rational Points
• On the discrete logarithm problem in finite fields of fixed characteristic
• On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
• The distribution of polynomials over finite fields

Cited in

(12)

• On complete \(m\)-arcs
• On construction and (non)existence of \(c\)-(almost) perfect nonlinear functions
• Investigating the exceptionality of scattered polynomials
• Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
• Algebraic constructions of complete \(m\)-arcs
• New results on quasi-subfield polynomials
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• On a conjecture on irreducible polynomials over finite fields with restricted coefficients
• Smoothness test for polynomials defined over small characteristic finite fields
• Exceptional scatteredness in prime degree
• Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
• Optimal selection for good polynomials of degree up to five

This page was built for publication: On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic

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