Paper 2021/527 Original: eprint.iacr.org/2021/527 ↗

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

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.