Efficient Lifting of Discrete Logarithms Modulo Prime Powers

We present a deterministic algorithm that, given a prime p and a solution x ∈ Z to the discrete logarithm problem aˣ ≡ b p with p a, efficiently lifts it to a solution modulo pᵏ, i.e., aˣ ≡ b pᵏ, for any fixed k ≥ 1. The algorithm performs k( log₂ p +2)+O(log p) multiplications modulo pᵏ in the worst case, improving upon prior lifting methods by at least a factor of 8.