On the signature calculus for finite fields of order square of prime numbers (Q2436760)

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.