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

DOI10.1137/18M1177196zbMATH Open1439.11297arXiv1706.08447WikidataQ127985122 ScholiaQ127985122MaRDI QIDQ5382575FDOQ5382575

Giacomo Micheli

Publication date: 18 June 2019

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Function Field Sieve and the Impact of Higher Splitting Probabilities
• A New Index Calculus Algorithm with Complexity $$L(1/4+o(1))$$ in Small Characteristic
• Algebraic Function Fields and Codes
• A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
• The distribution of polynomials over finite fields
• Exceptional Covers and Bijections on Rational Points
• On the discrete logarithm problem in finite fields of fixed characteristic
• A short proof of a Chebotarev density theorem for function fields

Cited In (9)

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

   Recommendations

• Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎
• Subquadratic-time factoring of polynomials over finite fields 👍 👎
• Title not available (Why is that?) 👍 👎
• A new efficient factorization algorithm for polynomials over small finite fields 👍 👎

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)