Selecting polynomials for the function field sieve

DOI10.1090/S0025-5718-2015-02940-8MaRDI QIDQ5501157zbMATH OpenFDO

Authors Razvan Barbulescu

Publication date 13 August 2015

Published in Mathematics of Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field GF(q^n), where q is small an prime power. The scope of this article is to select good polynomials for this algorithm by defining and measuring the size property and the so-called root and cancellation properties. In particular we present an algorithm for rapidly testing a large set of polynomials. Our study also explains the behaviour of inseparable polynomials, in particular we give an easy way to see that the algorithm encompass the Coppersmith algorithm as a particular case.

Recommendations

• scientific article; zbMATH DE number 2086903
• scientific article; zbMATH DE number 799769
• The Function Field Sieve in the Medium Prime Case
• Function field sieve method for discrete logarithms over finite fields
• scientific article; zbMATH DE number 1408416

Cites work

• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• Algorithms to solve the finite field discrete logarithm problem
• Breaking Pairing-Based Cryptosystems Using η T Pairing over GF(397)
• Fast evaluation of logarithms in fields of characteristic two
• Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields
• Function field sieve method for discrete logarithms over finite fields
• scientific article; zbMATH DE number 45380 (Why is no real title available?)
• scientific article; zbMATH DE number 47996 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 1313469 (Why is no real title available?)
• scientific article; zbMATH DE number 2086903 (Why is no real title available?)
• scientific article; zbMATH DE number 799769 (Why is no real title available?)
• scientific article; zbMATH DE number 862977 (Why is no real title available?)
• Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
• Non-linear polynomial selection for the number field sieve
• Solving a 676-bit discrete logarithm problem in \(\text{GF}(3^{6n})\)
• The Function Field Sieve in the Medium Prime Case
• The Magma algebra system. I: The user language

Cited in

(4)

• A general polynomial sieve.
• Faster initial splitting for small characteristic composite extension degree fields
• Levels of distribution for sieve problems in prehomogeneous vector spaces
• Some mathematical remarks on the polynomial selection in NFS

Describes a project that uses

Uses Software

• Magma

This page was built for publication: Selecting polynomials for the function field sieve

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