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 immediately 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.Category / Keywords: public-key cryptography / discrete logarithm problem, factoring, RSA, Shor's algorithm Date: received 1 Feb 2017, last revised 2 Feb 2017 Contact author: ekera at kth se Available format(s): PDF | BibTeX Citation Version: 20170206:185923 (All versions of this report) Short URL: ia.cr/2017/077 Discussion forum: Show discussion | Start new discussion