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 .