An algorithm for evaluation of discrete logarithms in some nonprime finite fields

Source abstract

In this paper we propose an algorithm for evaluation of logarithms in the finite fields F p n F_{p^n} , where the number p n − 1 p^n-1 has a small primitive factor r r . The heuristic estimate of the complexity of the algorithm is equal to exp ⁡ ( ( c + o ( 1 ) ) ( log ⁡ p r log 2 ⁡ r ) 1 / 3 ) \exp ((c+o(1))(\log p\,r\log ^2r)^{1/3}) , where n n grows to ∞ \infty , and p p is limited by a polynomial in n n . The evaluation of logarithms is founded on a new congruence of the kind of D. Coppersmith, C ( x ) k ≡ D ( x ) C(x)^k\equiv D(x) , which has a great deal of solutions—pairs of polynomials C ( x ) , D ( x ) C(x),D(x) of small degrees.