Practical Solving of Discrete Logarithm Problem over Prime Fields Using Quantum Annealing

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 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 F-11, over 5-bit prime field F-23 and over 6-bit prime field 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.