Study of the discrete logarithm problem in \(\mathbb{F}_{p^ 3}\) (Q1903546)

Let \(p\) be a prime number \(\geq 5\), \(k\) an irreducible polynomial in \(F_p [X]\) of degree 3 and \(g\) a generator of \(F^*_{p^3} = (F_p [X]/(k))^*\). The discrete logarithm problem in \(F^*_{p^3}\) is to determine \(x\) given \(y = g^x \in F_{p^3}\). Let \(m\) be a nonsquare in \(F_p\) and let \(E (\sqrt m)\) be the ring of integers of \(Q(\sqrt m)\). Previously, \textit{T. El Gamal} [IEEE Trans. Inf. Theory 31, 473--481 (1985; Zbl 0573.12006)] has given a subexponential algorithm for determining logarithms in \(F_{p^2}\) by establishing an isomorphism between \(F_{p^2}\) and \(E (\sqrt m)/(p)\) for \((p)\) a principal ideal of \(E (\sqrt m)\). The technique is extended here to fields of the form \(F_{p^3}\) by establishing an isomorphism between \(F_{p^3}\) and \(E ({\root 3 \of m})\) for \(m\) a noncube in \(F_p\) for \(p\equiv 1\pmod 3\). The algorithm is shown to have a running time of \(O (\exp (24 \sqrt {\log(p)\log\log(p)}))\).