Improvements to the number field sieve for non-prime finite fields
This work addresses computational challenges in cryptography for non-prime fields, representing an incremental improvement with specific practical gains.
The paper tackles the problem of computing discrete logarithms in non-prime finite fields by improving the Number Field Sieve, achieving a new theoretical complexity bound of L_p^n(1/3, √[3]{96/9}) and practically computing discrete logarithms in F_p^2 for an 80-digit prime.
We propose various strategies for improving the computation of discrete logarithms in non-prime fields of medium to large characteristic using the Number Field Sieve. This includes new methods for selecting the polynomials; the use of explicit automorphisms; explicit computations in the number fields; and prediction that some units have a zero virtual logarithm. On the theoretical side, we obtain a new complexity bound of $L_{p^n}(1/3,\sqrt[3]{96/9})$ in the medium characteristic case. On the practical side, we computed discrete logarithms in $F_{p^2}$ for a prime number $p$ with $80$ decimal digits.Warning: This unpublished version contains some inexact statements.