Welcome to the resource topic for 2016/537
Title:
A Generalisation of the Conjugation Method for Polynomial Selection for the Extended Tower Number Field Sieve Algorithm
Authors: Palash Sarkar, Shashank Singh
Abstract:In a recent work, Kim and Barbulescu showed how to combine previous polynomial selection methods with the extended tower number field sieve algorithm to obtain improved complexity for the discrete logarithm problem on finite fields \mathbb{F}_{p^n} for the medium prime case and where n is composite and not a prime-power. A follow up work by Sarkar and Singh presented a general polynomial selection method and showed how to lower the complexity in the medium prime case even when n is composite and a prime-power. This complexity, though, was higher than what was reported for the case of n composite and not a prime-power. By suitably combining the Conjugation method of polynomial selection proposed earlier by Barbulescu et al. with the extended tower number field sieve algorithm, Jeong and Kim showed that the same asymptotic complexity is achieved for any composite n. The present work generalises the polynomial selection method of Jeong and Kim for all composite n. Though the best complexity that can be achieved is not lowered, there is a significant range of finite fields for which the new algorithm achieves complexity which is lower than all previously proposed methods.
ePrint: https://eprint.iacr.org/2016/537
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 .