Paper 2008/064

Remarks on the NFS complexity

Pavol Zajac

Abstract

In this contribution we investigate practical issues with implementing the NFS algorithm to solve the DLP arising in XTR-based cryptosystems. We can transform original XTR-DLP to a DLP instance in $\mathbb{F}_{p^6},$ where $p$ is a medium sized prime. Unfortunately, for practical ranges of $p,$ the optimal degree of NFS polynomial is less than the required degree 6. This leads to a problem to find enough smooth equations during the sieve stage of the NFS algorithm. We discuss several techniques that can increase the NFS output, i.e. the number of equations produced during the sieve, without increasing the smoothness bound.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Submitted to: TATRA MOUNTAINS Mathematical Publications
Keywords
cryptanalysisdiscrete logarithm problemnumber field sieve
Contact author(s)
pavol zajac @ stuba sk
History
2008-02-11: received
Short URL
https://ia.cr/2008/064
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/064,
      author = {Pavol Zajac},
      title = {Remarks on the NFS complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2008/064},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/064}},
      url = {https://eprint.iacr.org/2008/064}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.