Cryptology ePrint Archive: Report 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 two contributions which are particularly relevant to the descent phase of the algorithm. The first contribution introduces a divisility 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 record computations of discrete logs for fields with 16 and 19-bit prime characteristic. Further, we provide concrete analysis of the effectiveness of the FFS algorithm for certain fields with medium sized prime characteristic.

Category / Keywords: public-key cryptography / discrete logarithm problem

Date: received 29 Jan 2014, last revised 30 Mar 2015

Contact author: sha2nk singh at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150330:120715 (All versions of this report)

Short URL: ia.cr/2014/065

Discussion forum: Show discussion | Start new discussion