Efficient Lifting of Discrete Logarithms Modulo Prime Powers

Giovanni Viglietta, Yasuyuki Kachi

We present a deterministic algorithm that, given a prime $p$ and a solution $x\in \mathbb{Z}$ to the discrete logarithm problem $a^x\equiv b(\mathrm{mod}p)$ with $p\nmid a$, efficiently…