Discrete Logarithms and Degree Six Number Field Sieve : A Practical Approach

ISBN-13: 9783639123319 / Angielski / Miękka / 2009 / 112 str.

Pavol Zajac

Opis

The asymptotically fastest algorithm to solve theDiscrete Logarithm Problem in finite fields is theNumber Field Sieve (NFS). This work presents asummary of the Number Field Sieve and its practicalexperimental implementation to solve the discretelogarithm problem in finite fields of degree six.This particular problem arises e.g. when one tries tosolve DLP in XTR cryptosystem. As shown, the degreesix instance of the DLP is practically more difficultto solve with NFS as a classical DLP. Also contained in this book are some specific remarksto the related topic of the polynomial selection forthe NFS. A three dimensional adaptation of the linesieving algorithm is described as well as theparametrization choices for the sieve region,contribution of small primes and exclusion of higherdegree ideals. Although the results of this work are related to thespecific instance of NFS, they can influence also themainstream NFS applications (the factoring ofintegers or the classical DLP).

O autorze

Author is currently a cryptology researcher at the Faculty of
Electrical Engineering and Information Technology, Slovak
University of Technology, Bratislava. His main research areas are
the discrete logarithm problem based cryptosystems, and the
design of ciphers (both modern and classical).