Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
type: Item
instance of: scholarly article
title: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
zbMATH Open document ID: 1485.68100
author: Martin Ekerå
published in: Journal of Mathematical Cryptology
publication date: 2021-08-05T00:00:00Z
review text: The author generalizes earlier works about a modified version of Shor's algorithm for computing short discrete logarithms with tradeoffs [\textit{M. Ekerå} and \textit{J. Håstad}, Lect. Notes Comput. Sci. 10346, 347--363 (2017; Zbl 1437.94058)]. The modified algorithm does not need the order of the group to be known because it computes both the order and the logarithm. However, it requires the logarithm to be small in comparison with the group order (`short discrete logarithm'). The paper also includes discussion of results of partial classical simulations of the suggested quantum algorithm.
reviewed by: Alexander Yu. Vlasov
Mathematics Subject Classification ID: 68Q12
Mathematics Subject Classification ID: 81P68
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7379095
zbMATH Keywords: quantum algorithms
zbMATH Keywords: discrete logarithms
zbMATH Keywords: order finding
zbMATH Keywords: Shor's algorithm
MaRDI profile type: Publication
full work available at URL: jmc-2020-0006
OpenAlex ID: W3161394282
cites work: On Lovász' lattice reduction and the nearest lattice point problem
cites work: New directions in cryptography
cites work: On post-processing in the quantum algorithm for computing short discrete logarithms
cites work: Quantum algorithms for computing short discrete logarithms and factoring RSA integers
cites work: The discrete logarithm modulo a composite hides \(O(n)\) bits
cites work: Factoring polynomials with rational coefficients
cites work: Riemann's hypothesis and tests for primality
cites work: Q4939150
cites work: An improved algorithm for computing logarithms over&lt;tex&gt;GF(p)&lt;/tex&gt;and its cryptographic significance (Corresp.)
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: A hierarchy of polynomial time lattice basis reduction algorithms
cites work: Lattice basis reduction: Improved practical algorithms and solving subset sum problems
cites work: Q2724450
cites work: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
DOI: 10.1515/JMC-2020-0006
Recommended article: Quantum computation of discrete logarithms in semigroups
Recommended article: Quantum algorithms for computing short discrete logarithms and factoring RSA integers
Recommended article: Q4847941
Recommended article: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Recommended article: On post-processing in the quantum algorithm for computing short discrete logarithms
Recommended article: Quantum algorithm for discrete logarithm problem for matrices over finite group rings
Recommended article: EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
Recommended article: Quantum algorithm for solving hyperelliptic curve discrete logarithm problem
Recommended article: Q3522446
description: scientific article; zbMATH DE number 7379095