Welcome to the resource topic for 2021/527
Title:
Practical solving of discrete logarithm problem over prime fields using quantum annealing
Authors: 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.
ePrint: https://eprint.iacr.org/2021/527
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .