Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Quantum algorithms for computing short discrete logarithms and factoring RSA integers
KTH, School of Computer Science and Communication (CSC). Swedish NCSA, Sweden.
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2017 (English)In: 8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017, Springer, 2017, Vol. 10346, p. 347-363Conference paper (Refereed)
Abstract [en]

We generalize the quantum algorithm for computing short discrete logarithms previously introduced by Ekerå [2] so as to allow for various tradeoffs between the number of times that the algorithm need be executed on the one hand, and the complexity of the algorithm and the requirements it imposes on the quantum computer on the other hand. Furthermore, we describe applications of algorithms for computing short discrete logarithms. In particular, we show how other important problems such as those of factoring RSA integers and of finding the order of groups under side information may be recast as short discrete logarithm problems. This gives rise to an algorithm for factoring RSA integers that is less complex than Shor’s general factoring algorithm in the sense that it imposes smaller requirements on the quantum computer. In both our algorithm and Shor’s algorithm, the main hurdle is to compute a modular exponentiation in superposition. When factoring an n bit integer, the exponent is of length 2n bits in Shor’s algorithm, compared to slightly more than n/2 bits in our algorithm.

Place, publisher, year, edition, pages
Springer, 2017. Vol. 10346, p. 347-363
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 10346
Keywords [en]
Discrete logarithms, Factoring, RSA, Shor’s algorithms
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-211962DOI: 10.1007/978-3-319-59879-6_20Scopus ID: 2-s2.0-85021747281ISBN: 9783319598789 (print)OAI: oai:DiVA.org:kth-211962DiVA, id: diva2:1133618
Conference
8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017, Utrecht, Netherlands, 26 June 2017 through 28 June 2017
Note

QC 20170816

Available from: 2017-08-16 Created: 2017-08-16 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Ekerå, MartinHåstad, Johan
By organisation
School of Computer Science and Communication (CSC)Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 127 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf