The number field sieve in the medium prime case. (English) Zbl 1161.11417

Joux, Antoine; Lercier, Reynald; Smart, Nigel; Vercauteren, Frederik

Dwork, Cynthia (ed.), Advances in cryptology – CRYPTO 2006. 26th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37432-9/pbk). Lecture Notes in Computer Science 4117, 326-344 (2006).

Summary: In this paper, we study several variations of the number field sieve to compute discrete logarithms in finite fields of the form \({\mathbb F}_{p^n}\), with \(p\) a medium to large prime. We show that when \(n\) is not too large, this yields a \(L_{p^n}(1/3)\) algorithm with efficiency similar to that of the regular number field sieve over prime fields. This approach complements the recent results of Joux and Lercier on the function field sieve. Combining both results, we deduce that computing discrete logarithms have heuristic complexity \(L_{p^n}(1/3)\) in all finite fields. To illustrate the efficiency of our algorithm, we computed discrete logarithms in a 120-digit finite field \({\mathbb F}_{p^3}\).
For the entire collection see [Zbl 1114.94001].

MSC:

11Y16	Number-theoretic algorithms; complexity
11T71	Algebraic coding theory; cryptography (number-theoretic aspects)
94A60	Cryptography