Welcome to the resource topic for
**2019/306**

**Title:**

Faster Initial Splitting for Small Characteristic Composite Extension Degree Fields

**Authors:**
Madhurima Mukhopadhyay, 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.

**ePrint:**
https://eprint.iacr.org/2019/306

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .