{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T19:50:19Z","timestamp":1723837819270},"reference-count":26,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order-finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.<\/jats:p>","DOI":"10.1515\/jmc-2020-0006","type":"journal-article","created":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T15:39:54Z","timestamp":1619192394000},"page":"359-407","source":"Crossref","is-referenced-by-count":13,"title":["Quantum algorithms for computing general discrete logarithms and orders with tradeoffs"],"prefix":"10.1515","volume":"15","author":[{"given":"Martin","family":"Eker\u00e5","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology , Stockholm , Sweden ; Swedish NCSA, Swedish Armed Forces , Stockholm , Sweden"}]}],"member":"374","published-online":{"date-parts":[[2021,4,22]]},"reference":[{"key":"2021081821075275856_j_jmc-2020-0006_ref_001","doi-asserted-by":"crossref","unstructured":"L. Babai, On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), no. 1, 1\u201313.","DOI":"10.1007\/BF02579403"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_002","doi-asserted-by":"crossref","unstructured":"E. Barker et al., Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, NIST SP 800\u201356A (2018), rev. 3.","DOI":"10.6028\/NIST.SP.800-56Ar3"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_003","doi-asserted-by":"crossref","unstructured":"W. Diffie and M.E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory 22 (1976), no. 6, 644\u2013654.","DOI":"10.1109\/TIT.1976.1055638"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_004","unstructured":"G. Einarsson, Probability Analysis of a Quantum Computer, ArXiv quant-ph\/0303074 (2003)."},{"key":"2021081821075275856_j_jmc-2020-0006_ref_005","unstructured":"M. Eker\u00e5, Modifying Shor's algorithm to compute short discrete logarithms, IACR ePrint Archive Report 2016\/1128 (2016)."},{"key":"2021081821075275856_j_jmc-2020-0006_ref_006","doi-asserted-by":"crossref","unstructured":"M. Eker\u00e5, On completely factoring any integer efficiently in a single run of an order finding algorithm, ArXiv 2007.10044 (2020).","DOI":"10.1007\/s11128-021-03069-1"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_007","doi-asserted-by":"crossref","unstructured":"M. Eker\u00e5, On post-processing in the quantum algorithm for computing short discrete logarithms, Des. Codes, Cryptogr. 88 (2020), no. 11, 2313\u20132335.","DOI":"10.1007\/s10623-020-00783-2"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_008","doi-asserted-by":"crossref","unstructured":"M. Eker\u00e5 and J. H\u00e5stad, Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: Lange T., Takagi T. (Eds) Post-Quantum Cryptography, PQCrypto 2017, LNCS (2017), no. 10346, 347\u2013363.","DOI":"10.1007\/978-3-319-59879-6_20"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_009","doi-asserted-by":"crossref","unstructured":"D. Gillmor, Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS), RFC 7919 (2016).","DOI":"10.17487\/RFC7919"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_010","doi-asserted-by":"crossref","unstructured":"R.B. Griffiths and C.-S. Niu, Semiclassical Fourier Transform for Quantum Computation, Phys. Rev. Lett. 76 (1996), no. 17, 3228\u20133231.","DOI":"10.1103\/PhysRevLett.76.3228"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_011","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, A. Schrift and A. Shamir, The Discrete Logarithm Modulo a Composite Hides O(n) bits, J. Comput. Syst. Sci. 47 (1993), no. 3, 376\u2013404.","DOI":"10.1016\/0022-0000(93)90038-X"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_012","doi-asserted-by":"crossref","unstructured":"R. Kannan, Improved algorithms for integer programming and related lattice problems. In: Proceedings of the 15th Symposium on the Theory of Computing, STOC \u201983 (1983), 99\u2014108.","DOI":"10.1145\/800061.808749"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_013","doi-asserted-by":"crossref","unstructured":"T. Kivinen and M. Kojo, More Modular Exponentiation (MODP) Diffie-Hellman groups for Internet Key Exchange, RFC 3526 (2003).","DOI":"10.17487\/rfc3526"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_014","unstructured":"A. Koenecke and P. Wocjan, Recovering the period in Shor's algorithm with Gauss\u2019 algorithm for lattice basis reduction, ArXiv 1210.3003 (2013)."},{"key":"2021081821075275856_j_jmc-2020-0006_ref_015","doi-asserted-by":"crossref","unstructured":"A. Korkine and G. Zolotareff, Sur les formes quadratiques, Math. Ann. 6 (1873), no. 3, 366\u2013389.","DOI":"10.1007\/BF01442795"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_016","doi-asserted-by":"crossref","unstructured":"H.W. Lenstra, A.K. Lenstra and L. Lov\u00e1sz, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982), no. 4, 515\u2013534.","DOI":"10.1007\/BF01457454"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_017","doi-asserted-by":"crossref","unstructured":"G.L. Miller, Riemann's hypothesis and tests for primality, J. Comput. Syst. Sci. 13 (1976), no. 3, 300\u2013317.","DOI":"10.1016\/S0022-0000(76)80043-8"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_018","doi-asserted-by":"crossref","unstructured":"M. Mosca and A. Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In: Proceeding from the First NASA International Conference, QCQC \u201998, LNCS (1999), no. 1509, 174\u2013188.","DOI":"10.1007\/3-540-49208-9_15"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_019","doi-asserted-by":"crossref","unstructured":"S. Parker and M.B. Plenio, Efficient Factorization with a Single Pure Qubit and log N Mixed Qubits, Phys. Rev. Lett. 85 (2000), no. 14, 3049\u20133052.","DOI":"10.1103\/PhysRevLett.85.3049"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_020","doi-asserted-by":"crossref","unstructured":"S.C. Pohlig and M.E. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance, IEEE Trans. Inf. Theory 24 (1978), no. 1, 106\u2013110.","DOI":"10.1109\/TIT.1978.1055817"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_021","doi-asserted-by":"crossref","unstructured":"R.L. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Commun. ACM 21 (1978), no. 2, 120\u2013126.","DOI":"10.1145\/359340.359342"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_022","doi-asserted-by":"crossref","unstructured":"C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci. 53 (1987), no. 2\u20133, 201\u2013224.","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_023","doi-asserted-by":"crossref","unstructured":"C.-P. Schnorr and M. Euchner: Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program. 66 (1994), no. 1\u20133, 181\u2013199.","DOI":"10.1007\/BF01581144"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_024","doi-asserted-by":"crossref","unstructured":"J.-P. Seifert, Using fewer qubits in Shor's factorization algorithm via simultaneous Diophantine approximation. In: Naccache, D. (ed.) CT-RSA 2001, LNCS (2001), no. 2020, 319\u2013327.","DOI":"10.1007\/3-540-45353-9_24"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_025","unstructured":"P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS \u201994 (1994), 124\u2013134"},{"key":"2021081821075275856_j_jmc-2020-0006_ref_026","doi-asserted-by":"crossref","unstructured":"P.W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997), no. 5, 1484\u20131509.","DOI":"10.1137\/S0097539795293172"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0006\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0006\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,18]],"date-time":"2021-08-18T21:24:35Z","timestamp":1629321875000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0006\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,11,17]]},"published-print":{"date-parts":[[2020,11,17]]}},"alternative-id":["10.1515\/jmc-2020-0006"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2020-0006","relation":{},"ISSN":["1862-2984"],"issn-type":[{"value":"1862-2984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,1]]}}}  <script>parent.window.postMessage('ixistenz.url:https://api.crossref.org/works/10.1515%2FJMC-2020-0006', '*'); </script> <div id='browserdiffcontainer' style='position: fixed; right: 10px; top: 10vh; min-width: 60px;  border: 1px solid white; background: rgb(251, 189, 0);; opacity: 0.9; font-family: helvetica, arial, sans serif;  font-size: 12px; z-index: 20001; padding-bottom: 20px;'><div onclick="toggle('browserdiffcontainerlist'); return false;" style='background: rgb(151, 89, 0);; color: white; '><strong>&nbsp; <span class='glyphicon glyphicon-minus'></span> NODES</strong></div><div id='browserdiffcontainerlist' style='padding-left: 10px; padding-right: 5px; max-height: 50vh; overflow: auto; '><div><a href='#diffid123' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:123', '*');; return false;" style='text-decoration: none; '>INTERN </a> <a style='color: white;' href='#diffid123'><sup>2</sup></a></div></div></div>
<script>
function toggle( divname ) {
  var x = document.getElementById( divname );
  if (x.style.display === 'none') {
    x.style.display = 'block';
  } else {
    x.style.display = 'none';
  }
} </script>