You are looking at a specific version 20150911:104905 of this paper. See the latest version.

Paper 2014/641

The Multiple Number Field Sieve with Conjugation Method

Cécile Pierrot

Abstract

In this short paper, we propose a variant of the Number Field Sieve to compute discrete logarithms in medium characteristic finite fields. We propose an algorithm that combines two recent ideas, namely the Multiple variant of the Number Field Sieve taking advantage of a large number of number fields in the sieving phase and the Conjugation Method giving a new polynomial selection for the classical Number Field Sieve. The asymptotic complexity of our improved algorithm is L_Q (1/3, (8 (9+4 \sqrt{6})/15)^1/3), where F_Q is the target finite field and (8 (9+4 \sqrt{6})/15)^1/3) is approximately equal to 2.156. This has to be compared with the complexity of the previous state-of-the-art algorithm for medium characteristic finite fields, the Number Field Sieve with Conjugation Method, that has a complexity of approximately L_Q(1/3, 2.201).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Discrete LogarithmFinite FieldMedium CharacteristicNFS
Contact author(s)
Cecile Pierrot @ lip6 fr
History
2015-09-11: revised
2014-08-27: received
See all versions
Short URL
https://ia.cr/2014/641
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.