Paper 2016/537

A Generalisation of the Conjugation Method for Polynomial Selection for the Extended Tower Number Field Sieve Algorithm

Palash Sarkar and 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
finite fieldsdiscrete logarithmtower number field sieve
Contact author(s)
palash @ isical ac in
History
2016-05-31: received
Short URL
https://ia.cr/2016/537
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/537,
      author = {Palash Sarkar and Shashank Singh},
      title = {A Generalisation of the Conjugation Method for Polynomial Selection for the Extended Tower Number Field Sieve Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2016/537},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/537}},
      url = {https://eprint.iacr.org/2016/537}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.