**Faster Initial Splitting for Small Characteristic Composite Extension Degree Fields**

*Madhurima Mukhopadhyay and Palash Sarkar*

**Abstract: **Let $p$ be a small prime and $n=n_1n_2>1$ be a composite integer.
For the function field sieve algorithm applied to $\mathbb{F}_{p^n}$, 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 $\mathbb{F}_{p^{n_1}}$.
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(1/\pi))$ multiplications in $\mathbb{F}_p$, where $\pi$ is the relevant smoothness probability.

**Category / Keywords: **public-key cryptography / Discrete Log, Finite fields, Function Field Sieve, Cryptography

**Date: **received 18 Mar 2019

**Contact author: **palash at isical ac in, madhurima_r@isical ac in

**Available format(s): **PDF | BibTeX Citation

**Version: **20190320:103306 (All versions of this report)

**Short URL: **ia.cr/2019/306

[ Cryptology ePrint archive ]