Lifting of solutions of an exponential congruence (Q881059): Difference between revisions

Let \(K\) be a finite extension of \(\mathbb Q\), \(n=[K:{\mathbb Q}]\), and \({\mathbb Z}_K\) be the ring of integers of \(K\). Let \(\mathfrak p\) be a prime ideal of \({\mathbb Z}_K\), and \(\alpha,\beta\in{\mathbb Z}\) be such that \(\alpha,\beta\in{\mathfrak p}\). In the paper a polynomial algorithm is suggested for reducing the discrete logarithm problem, i.e. of reducing the solution of the congruence \(\alpha^x\equiv \beta \bmod{{\mathfrak p}^N}\), \(N>1\) an integer, to the solution of the \(\alpha^x\equiv \beta \bmod{{\mathfrak p}}\), \(x\in {\mathbb Z}\). The solution is divided into three parts: the ``degenerate'' case in which \(\alpha\) is a root of degree \(p^f-1\) of \(1\) \(\bmod{ {\mathfrak p}^N}\), and the ``lower'' and ``higher'' cases in which \(N\) is not greater than \(\rho=\lfloor e/(p-1)\rfloor+1\) and greater that \(\rho\), with standard meaning of \(e,f\) and \(p\). In the presented explicit formulas instead of the Fermat quotients polynomially computable logarithmic functions are used, and \(\rho\) appears here because of the convergence of the series in use.