Efficient Lifting of Discrete Logarithms Modulo Prime Powers

Abstract

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 lifts it to a solution modulo $p^k$, i.e., $a^x\equiv b(\mathrm{mod}{p}^k)$, for any fixed $k\ge 1$. The algorithm performs $k(\lceil {\log }_{2}p\rceil +2)+O(\log p)$ multiplications modulo $p^k$ in the worst case, improving upon prior lifting methods by at least a factor of 8.

15 pages