**Solving discrete logarithm problem over prime fields using quantum annealing and $\frac{n^3}{2}$ logical qubits**

*Michał Wroński*

**Abstract: **Shor's quantum algorithm for integer factorization and discrete logarithm is one of the fundamental approaches in modern cryptology. The application of Shor's algorithm requires a general-purpose quantum computer. On the other hand, there are known methods of transformation of factorization problem to the QUBO problem and then solving it using quantum annealing computing with approximately $\frac{n^2}{4}$ logical qubits, for example, using D-Wave computer. It is believed that this approach also may be helpful, primarily until large general-purpose quantum computers will exist. Until now algorithm of similar efficiency for computing discrete logarithm over prime fields was unknown. In this paper, we present a method of reducing discrete logarithm problem to the QUBO problem, which requires approximately $\frac{n^3}{2}$ logical qubits. We also show how to apply quantum annealing to compute discrete logarithm modulo composite numbers, where a quantum annealing factorization algorithm may be used to reduce discrete logarithm modulo composite to several discrete logarithm problems modulo prime number.

**Category / Keywords: **public-key cryptography / discrete logarithm problem, D-Wave, quantum annealing, cryptanalysis

**Date: **received 21 Apr 2021

**Contact author: **michal wronski at wat edu pl

**Available format(s): **PDF | BibTeX Citation

**Version: **20210423:122550 (All versions of this report)

**Short URL: **ia.cr/2021/527

[ Cryptology ePrint archive ]