On the signature calculus for finite fields of order square of prime numbers
The hardness of the calculation of discrete logarithms ensures the security of a lot of public-key encryption systems, therefore knowing an estimate for the complexity of the computation is of great importance. In the case of a finite field \(\mathbb F_q\), where \(q=p^k\) is the power of a prime number, the best known algorithms are the number theory sieve, when \(k=1\), and the function field sieve or a modified number field sieve, when \(k>1\). The running time of the number field sieve is conjectured to be \(L_p(\alpha,c)=\exp((c+o(1))(\log p)^{\alpha}(\log\log p)^{1-\alpha})\), with \(\alpha=1/3\) and \(c=(64/9)^{1/3}\). The function field sieve and the modified number field sieve conjecturally have running times \(L_q(\max\{1/3,1-e\},O(1))\) and \(L_q(\max\{1/3,(1+e)/4\},O(1))\) respectively, where \(e\) is the real number such that \(k=(\log q/\log \log q)^e\). In [\textit{M.-D. Huang} and \textit{W. Raskind}, LMS J. Comput. Math. 12, 228--263 (2009; Zbl 1236.11110)], a different kind of approach is described. More precisely, the authors relate the discrete logarithm problem to some classical problems in algebraic number theory and arithmetic geometry, such as the calculation of class fields for real quadratic fields. However it is unclear whether this will lead to more efficient algorithms for computing discrete logarithms. The paper under review starts with a short general introduction, followed by a section devoted to the definition of the so-called ramification signature for a real quadratic field. In the last section the main result is proved, namely that the discrete logarithm problem in \(\mathbb F_{p^2}\) is random polynomial time equivalent to computing the ramification signature of some real quadratic field. This extends a result from [loc. cit.], in which the case of a prime field \(\mathbb F_p\) was considered.
- Discrete logarithms and local units
- Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
- Function field sieve method for discrete logarithms over finite fields
- Global duality, signature calculus and the discrete logarithm problem
- scientific article; zbMATH DE number 3674235 (Why is no real title available?)
- scientific article; zbMATH DE number 799769 (Why is no real title available?)
- Reducing elliptic curve logarithms to logarithms in a finite field
- Using number fields to compute logarithms in finite fields
This page was built for publication: On the signature calculus for finite fields of order square of prime numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436760)
