Paper 2014/065
Fine Tuning the Function Field Sieve Algorithm for the Medium Prime Case
Palash Sarkar and Shashank Singh
Abstract
This work builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and
Lercier in 2006. We make several contributions. The first contribution uses a divisibility and smoothness technique and goes
on to develop a sieving method based on the technique. This leads to significant practical efficiency improvements in the descent phase
and also provides improvement to Joux's pinpointing technique. The second contribution is a detailed analysis of the degree of freedom
and the use of a walk technique in the descent phase of the algorithm. Such analysis shows that it is possible to compute discrete
logarithms over certain fields which are excluded by the earlier analyses performed by Joux and Lercier (2006) and Joux (2013). In
concrete terms, we present computations of discrete logs for fields with 16 and 19-bit prime characteristic. We also
provide concrete analysis of the effectiveness of the FFS algorithm for certain fields of characteristic ranging from 16-bit to
32-bit primes. The final contribution is to perform a complete asymptotic analysis of the FFS algorithm for fields
Note: A rounding error in the published version in IEEE.IT has been corrected.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. IEEE Transactions on Information Theory
- DOI
- 10.1109/TIT.2016.2528996
- Keywords
- discrete logarithm problem
- Contact author(s)
- sha2nk singh @ gmail com
- History
- 2020-03-04: last of 4 revisions
- 2014-01-29: received
- See all versions
- Short URL
- https://ia.cr/2014/065
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/065,
author = {Palash Sarkar and Shashank Singh},
title = {Fine Tuning the Function Field Sieve Algorithm for the Medium Prime Case},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/065},
year = {2014},
doi = {10.1109/TIT.2016.2528996},
url = {https://eprint.iacr.org/2014/065}
}
