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

Authors: 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

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

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

• 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}}\)
• A new index calculus algorithm with complexity \(L(1/4+o(1))\) in small characteristic
• Algebraic Function Fields and Codes
• Title not available (Why is that?)
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• The distribution of polynomials over finite fields
• Title not available (Why is that?)
• 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 (12)

• Smoothness test for polynomials defined over small characteristic finite fields
• Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• 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
• New results on quasi-subfield polynomials

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)