Using number fields to compute logarithms in finite fields

摘要

We describe an adaptation of the number field sieve to the problem of computing logarithms in a finite field. We conjecture that the running time of the algorithm, when restricted to finite fields of an arbitrary but fixed degree, is L-q[1/3; (64/9)(1/3) + o(1)], where q is the cardinality of the field, L-q[s; c] = exp(c(log q)(s)(log log q)(1-s)), and the o(1) is for q --> infinity. The number field sieve factoring algorithm is conjectured to factor a number the size of q in the same amount of time. [References: 36]