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.
展开▼
机译:我们提出了多种策略,以改进使用Number Field Sieve的中到大特征非素数字段中离散对数的计算。这包括选择多项式的新方法。显式自同构的使用;数字字段中的显式计算;并预测某些单位的虚拟对数为零。从理论上讲,在中等特征情况下,我们获得了新的复杂度界限$ L_ {p ^ n}(1/3, sqrt [3] {96/9})$。在实际方面,我们为带有$ 80 $十进制数字的质数$ p $计算了在$ F_ {p ^ 2} $中的离散对数。
展开▼