2
$\begingroup$

Could someone write Shor's algorithm for solving the discrete logarithm problem and how it could apply to elliptic curves in a few, easy to understand steps? I have a basic understanding of quantum computing, but not enough to understand his paper.

$\endgroup$

1 Answer 1

6
$\begingroup$

Could one adapt Shor's algorithm to solve the DLP? Yes: Shor's original paper (arXiv preprint) explains how, in §6 on p. 321.

Could one adapt Shor's algorithm to solve the ECDLP? Yes. Researchers at Microsoft recently published estimates for how big a quantum computer you would need to do so. (Spoiler: Smaller than RSA at comparable classical security levels.)

Could one write down how it works in a few easy-to-understand steps? Maybe, but that's above my pay grade at the moment if you find those two papers to obscure! You might start with Scott Aaronson's article on Shor's algorithm, see if you can find the hidden subgroup problem hidden in the algorithm, and adapt it to the hidden subgroup problem in discrete logs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.