Relation collection for the Function Field Sieve

Jérémie Detrey, Pierrick Gaudry, and Marion Videau

Abstract

In this paper, we focus on the relation collection step of the Function Field Sieve (FFS), which is to date the best algorithm known for computing discrete logarithms in small-characteristic finite fields of cryptographic sizes. Denoting such a finite field by GF(p^n), where p is much smaller than n, the main idea behind this step is to find polynomials of the form a(t)-b(t)x in GF(p)[t][x] which, when considered as principal ideals in carefully selected function fields, can be factored into products of low-degree prime ideals. Such polynomials are called "relations", and current record-sized discrete-logarithm computations need billions of those. Collecting relations is therefore a crucial and extremely expensive step in FFS, and a practical implementation thereof requires heavy use of cache-aware sieving algorithms, along with efficient polynomial arithmetic over GF(p)[t]. This paper presents the algorithmic and arithmetic techniques which were put together as part of a new public implementation of FFS, aimed at medium- to record-sized computations.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. To be presented at ARITH 2013.
Keywords
function field sievediscrete logarithmpolynomial arithmeticfinite-field arithmetic
Contact author(s)
Jeremie Detrey @ loria fr
History
Short URL
https://ia.cr/2013/071

CC BY

BibTeX

@misc{cryptoeprint:2013/071,
author = {Jérémie Detrey and Pierrick Gaudry and Marion Videau},
title = {Relation collection for the Function Field Sieve},
howpublished = {Cryptology ePrint Archive, Paper 2013/071},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/071}},
url = {https://eprint.iacr.org/2013/071}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.