Paper 2019/306

Faster Initial Splitting for Small Characteristic Composite Extension Degree Fields

Madhurima Mukhopadhyay and Palash Sarkar

Abstract

Let $$ be a small prime and $$ be a composite integer. For the function field sieve algorithm applied to $$, Guillevic (2019) had proposed an algorithm for initial splitting of the target in the individual logarithm phase. This algorithm generates polynomials and tests them for $$-smoothness for some appropriate value of $$. The amortised cost of generating each polynomial is $$ multiplications over $$. In this work, we propose a new algorithm for performing the initial splitting which also generates and tests polynomials for $$-smoothness. The advantage over Guillevic splitting is that in the new algorithm, the cost of generating a polynomial is $$ multiplications in $$, where $$ is the relevant smoothness probability.