Paper 2026/1216

New Quantum-Classical Algorithm or the Discrete Logarithm Problem over $\mathbb{Z}_{p}^{*}$

Abstract

Shor demonstrated that the discrete logarithm problem in the multiplicative roup $\mathbb{Z}_{p}^{*}$, where $p$ is an odd prime, can be solved fficiently using a period-finding algorithm based on the quantum Fourier transform. In this paper, we propose a quantum-classical algorithm based on algebraic properties that do not rely on periodicity. Specifically, we show that the hardcore predicate for the discrete logarithm problem, which was introduced by Blum and Micali, can be reduced, using the swap test, to the problem of distinguishing between two Bernoulli distributions. In our algorithm, although the swap test is used as a quantum subroutine, most of the computation is performed classically. Moreover, the algorithm does not require the quantum Fourier transform.