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

A Quantum "Magic Box" for the Discrete Logarithm Problem.

Burton S. Kaliski

Published Jan 1, 2017• 4 citations
OpenAlex

Related papers

Quantum Complexity for Discrete Logarithms and Related Problems

Minki Hhan, Takashi Yamakawa, Aaram Yun

arXiv:2307.03065•Lecture notes in computer science•Jan 1, 2024•12 citations

A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret +1 more

arXiv:2209.02814•Lecture notes in computer science•Jan 1, 2024•4 citations

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

Michał Wroński

Lecture notes in computer science•Jan 1, 2022•7 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•33 citations

Quantum computation of discrete logarithms in semigroups

Andrew M. Childs, Gábor Ivanyos

Abstract We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and the discrete logarithm problem as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete logarithm problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete logarithm problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to k ≥ 2 generators in a black-box abelian semigroup of order N requires Θ ˜ ( N 1 2 - 1 2 k ) $\tilde{\Theta }(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries.

arXiv:1310.6238•Journal of Mathematical Cryptology•Jul 8, 2014•32 citations

Quantum Computing for Discrete Logarithms

Song Yuan Yan

Springer eBooks•Jan 1, 2015•3 citations
Abstract We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and the discrete logarithm problem as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete logarithm problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete logarithm problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to k ≥ 2 generators in a black-box abelian semigroup of order N requires Θ ˜ ( N 1 2 - 1 2 k ) Θ~(N12−12k)\tilde{\Theta }(N^{\frac{1}{2}-\frac{1}{2k}})Θ~(N21​−2k1​) quantum queries.