An optimization approach for the discrete logarithm problem

Abstract

The discrete logarithm problem has remained challenging to tackle, resulting in its wide use in cryptography. The only proven way to solve the problem in polynomial time is through Shor’s algorithm, which runs on quantum computers, but present-day quantum com- puters are subjected to quantum errors when implementing Shor’s algorithm. However, quantum annealers such as the D-Wave ma- chine have come a long way. Further, another problem similar to the discrete logarithm problem, the prime factoring problem, has shown much progress on quantum annealers. In this context, it is encour- aging to see the tractability of the discrete logarithm problem on quantum annealers. Further, the problem is scarcely attempted as an optimization. In this work, we have represented a conversion of the discrete loga- rithm problem over the multiplicative group integer modulo and the elliptic curve discrete logarithm problem to an optimization problem, then to a binary quadratic form accepted by quantum annealers. Fur- ther, we tested our formulation for small scale problems successfully and discussed the complexities suggesting areas of improvement.