Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

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

Michał Wroński

Published Jan 1, 2022• 6 citations
Publisher
DOI
10.1007/978-3-031-08760-8_8

Related papers

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

Micha, Wro, ski

•Jan 1, 2021•0 citations

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

Michał Wroński

•Jan 1, 2021•1 citation

Index Calculus Method for Solving Elliptic Curve Discrete Logarithm Problem Using Quantum Annealing

Michał Wroński

Lecture notes in computer science•Jan 1, 2021•6 citations

Quantum algorithm for solving hyperelliptic curve discrete logarithm problem

Yan Tang Huang, Zhaofeng Su, Fangguo Zhang +2 more

Quantum Information Processing•Jan 2, 2020•31 citations

Quantum circuits for hyperelliptic curve discrete logarithms over the Mersenne prime fields

Chao Chen, Peidong Guan, Yan Tang Huang +1 more

Quantum Information Processing•Jul 5, 2023•4 citations

Base of exponent representation matters -- more efficient reduction of discrete logarithm problem and elliptic curve discrete logarithm problem to the QUBO problem

Michał Wroński, Łukasz Dzierzkowski

This paper presents further improvements in the transformation of the Discrete Logarithm Problem (DLP) and Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. This is significant from a cryptanalysis standpoint, as QUBO problems may be solved using quantum annealers, and the fewer variables the resulting QUBO problem has, the less time is expected to obtain a solution.The main idea presented in the paper is allowing the representation of the exponent in different bases than the typically used base 2 (binary representation). It is shown that in such cases, the reduction of the discrete logarithm problem over the prime field \(\mathbb{F}_p\) to the QUBO problem may be obtained using approximately \(1.89n^2\) logical variables for \(n\) being the bitlength of prime \(p\), instead of the \(2n^2\) which was previously the best-known reduction method. The paper provides a practical example using the given method to solve the discrete logarithm problem over the prime field \(\mathbb{F}_{47}\). Similarly, for the elliptic curve discrete logarithm problem over the prime field \(\mathbb{F}_p\), allowing the representation of the exponent in different bases than typically used base two results in a lower number of required logical variables for \(n\) being the bitlength of prime \(p\), from \(3n^3\) to \(\frac{6n^3}{\log_{2}\left(\frac{3}{4}n\right)}\) logical variables, in the case of Edwards curves.

Quantum Information and Computation•Jun 1, 2024•2 citations
Solving discrete logarithm problem over prime fields using quantum annealing and n32\frac{n^3}{2}2n3​ logical qubits
Solving discrete logarithm problem over prime fields using quantum annealing and n32\frac{n^3}{2}2n3​ logical qubits.
This paper presents further improvements in the transformation of the Discrete Logarithm Problem (DLP) and Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. This is significant from a cryptanalysis standpoint, as QUBO problems may be solved using quantum annealers, and the fewer variables the resulting QUBO problem has, the less time is expected to obtain a solution.The main idea presented in the paper is allowing the representation of the exponent in different bases than the typically used base 2 (binary representation). It is shown that in such cases, the reduction of the discrete logarithm problem over the prime field Fp\mathbb{F}_pFp​ to the QUBO problem may be obtained using approximately 1.89n21.89n^21.89n2 logical variables for nnn being the bitlength of prime ppp, instead of the 2n22n^22n2 which was previously the best-known reduction method. The paper provides a practical example using the given method to solve the discrete logarithm problem over the prime field F47\mathbb{F}_{47}F47​. Similarly, for the elliptic curve discrete logarithm problem over the prime field Fp\mathbb{F}_pFp​, allowing the representation of the exponent in different bases than typically used base two results in a lower number of required logical variables for nnn being the bitlength of prime ppp, from 3n33n^33n3 to 6n3log⁡2(34n)\frac{6n^3}{\log_{2}\left(\frac{3}{4}n\right)}log2​(43​n)6n3​ logical variables, in the case of Edwards curves.