Complexity of a determinate algorithm for the discrete logarithm (Q1898267): Difference between revisions

Let \(\langle G,\cdot \rangle\) be a finite group and \(g, a\in G\). Let \(g\) be an element of order \(t\) and \(n\), \(k\), \(m\) be natural numbers. Consider the equation \(g^x= a\), \(x\in \mathbb{N}\). To determine \(x\), suppose \(km\geq t\) and compute the products \(a, ag, \dots, ag^{m-1}\) and \(g^m, g^{2m}, \dots, g^{km}\). Then if, for some \(i\), \(j\), \(g^{mi}= ag^j\) then \(n= mi-j\) is a solution. This is the well known Shanks baby-step, giant-step algorithm which requires on the order of \(2\sqrt {t}\) multiplications. It is established in this paper that, among a certain class of algorithms, this algorithm is optimal in a certain sense.