Paper 2019/306
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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. Minor revision.
 Keywords
 Discrete LogFinite fieldsFunction Field SieveCryptography
 Contact author(s)

palash @ isical ac in
madhurima_r @ isical ac in  History
 20190320: received
 Short URL
 https://ia.cr/2019/306
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/306, author = {Madhurima Mukhopadhyay and Palash Sarkar}, title = {Faster Initial Splitting for Small Characteristic Composite Extension Degree Fields}, howpublished = {Cryptology ePrint Archive, Paper 2019/306}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/306}}, url = {https://eprint.iacr.org/2019/306} }