Study of the discrete logarithm problem in F_p^ 3
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)}))\).
- A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields
- On Computing Logarithms Over Finite Fields
- A subexponential-time algorithm for computing discrete logarithms over<tex>GF(p^2)</tex>
- Computation of discrete logarithms in an arbitrary finite field
- scientific article; zbMATH DE number 3863322
- A classical invitation of algebraic numbers and class fields. With two appendices by Olga Taussky: ``Artin's 1932 Göttingen lectures on class field theory and ``Connections between algebraic number theory and integral matrices.
- A subexponential-time algorithm for computing discrete logarithms over<tex>GF(p^2)</tex>
- Fast Computation of Discrete Logarithms in GF (q)
- scientific article; zbMATH DE number 4023423 (Why is no real title available?)
- scientific article; zbMATH DE number 3233757 (Why is no real title available?)
- scientific article; zbMATH DE number 3404329 (Why is no real title available?)
- The Euclidean Condition in Pure Cubic and Complex Quartic Fields
- Factor base discrete logarithms in Kummer extensions
- A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields
- What is the inverse of repeated square and multiply algorithm?
- A subexponential-time algorithm for computing discrete logarithms over<tex>GF(p^2)</tex>
- Discrete Restriction for (x,x3) and Related Topics
- Lifting of solutions of an exponential congruence
This page was built for publication: Study of the discrete logarithm problem in \(\mathbb{F}_{p^ 3}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1903546)
