International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Remarks on the NFS complexity

Authors:
Pavol Zajac
Download:
URL: http://eprint.iacr.org/2008/064
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17741,
  title={Remarks on the NFS complexity},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / cryptanalysis, discrete logarithm problem, number field sieve},
  url={http://eprint.iacr.org/2008/064},
  note={Submitted to: TATRA MOUNTAINS Mathematical Publications pavol.zajac@stuba.sk 13913 received 4 Feb 2008},
  author={Pavol Zajac},
  year=2008
}