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 two contributions. The first contribution introduces a divisility and smoothness technique which is similar to that of the special-q technique used in integer factorisation algorithms. Such a technique, though, has not been earlier used in the context of discrete log computations and provides concrete speed-ups in the practical run-time of the relation collection and the descent phases of the FFS algorithm. The second contribution is to improve the descent phase of the algorithm. The improvements are based on increasing the degree of freedom and the use of a walk technique. As a consequence, we show that it is feasible to carry out discrete log computations for certain fields which are excluded by the analysis of Joux and Lercier. In concrete terms, we present record computations of discrete logs for fields with 16 and 18-bit prime characteristic. Further, we provide concrete analysis of the effectiveness of the FFS algorithm for certain fields with medium sized prime characteristic.