Faster initial splitting for small characteristic composite extension degree fields

摘要

Let p be a small prime and n = n(1)n(2) 1 be a composite integer. For the function field sieve algorithm applied to F-pn, 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 B-smoothness for some appropriate value of B. The amortised cost of generating each polynomial is O(n(2)(2)) multiplications over F-pn1. In this work, we propose a new algorithm for performing the initial splitting which also generates and tests polynomials for B-smoothness. The advantage over Guillevic splitting is that in the new algorithm, the cost of generating a polynomial is O(n log(p) (1/pi)) multiplications in F-p, where pi is the relevant smoothness probability. (C) 2019 Elsevier Inc. All rights reserved.