Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T05:07:17.669Z Has data issue: false hasContentIssue false

The multiple number field sieve for medium- and high-characteristic finite fields

Published online by Cambridge University Press:  01 August 2014

Razvan Barbulescu
Affiliation:
Université de Lorraine, France email razvan.barbulescu@inria.fr
Cécile Pierrot
Affiliation:
Laboratoire d’Informatique de Paris 6, UPMC, France email Cecile.Pierrot@lip6.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we study the discrete logarithm problem in medium- and high-characteristic finite fields. We propose a variant of the number field sieve (NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}\mathbb{F}_{p^n}$ for the whole range of applicability of the NFS and lowers the asymptotic complexity from $L_{p^n}({1/3},({128/9})^{1/3})$ to $L_{p^n}({1/3},(2^{13}/3^6)^{1/3})$ in the medium-characteristic case, and from $L_{p^n}({1/3},({64/9})^{1/3})$ to $L_{p^n}({1/3},((92 + 26 \sqrt{13})/27)^{1/3})$ in the high-characteristic case.