Paper 2021/527

Practical solving of discrete logarithm problem over prime fields using quantum annealing

Michał Wroński

Abstract

This paper investigates how to reduce discrete logarithm problem over prime fields to the QUBO problem to obtain as few logical qubits as possible. We show different methods of reduction of discrete logarithm problem over prime fields to the QUBO problem. In the best case, if $n$ is the bitlength of a characteristic of the prime field $\mathbb F_p$, there are required approximately $2n^2$ logical qubits for such reduction. We present practical attacks on discrete logarithm problem over the $4$-bit prime field $\mathbb F_{11}$, over $5$-bit prime field $\mathbb F_{23}$ and over $6$-bit prime field $\mathbb F_{59}$. We solved these problems using D-Wave Advantage QPU. It is worth noting that, according to our knowledge, until now, no one has made a practical attack on discrete logarithm over the prime field using quantum methods.

Note: This paper is the upgraded and revised version of the previous version of the paper. We changed the title from "Solving discrete logarithm problem over prime fields using quantum annealing and $\frac{n^3}{2}$ logical qubits" to "Practical solving of discrete logarithm problem over prime fields using quantum annealing." The current version presents a better method of reducing the discrete logarithm problem to the QUBO problem than in the previous version of the paper. What's more, we did practical experiments, and we described these experiments in the current version of the paper.