## Shor madness

Bruce Schneier points to post on Emergent Chaos, which gives a very bleak outlook for quantum computers being used to break public key cryptosystems.

The crypto-obviating algorithms in question are Shor’s algorithm for factoring and an algorithm he developed for discrete logs. I was surprised to learn that Shor’s algorithm requires 72k

^{3}quantum gates to be able to factor a umber k bits long. Cubed is a somewhat high power. So I decided to look at a 4096-bit RSA key, which is the largest that most current software supports — the crypto experts all say that if you want something stronger, you should shift to elliptic curve, and the US government is pushing this, too, with their “Suite B” algorithms.

To factor a 4096-bit number, you need 72*4096^{3}or 4,947,802,324,992 quantum gates. Lets just round that up to an even 5 trillion. Five trillion is a big number. We’re only now getting to the point that we can put about that many normal bits on a disk drive. The first thing this tells me is that we aren’t going to wake up one day and find out that someone’s put that many q-gates on something you can buy from Fry’s from a white-box Taiwanese special.

So what’s wrong with this? The Quantum Pontiff defends the faith.

There is however one point which he, and apparently everyone commenting on this story, missed. The slow part of Shor’s algorithm is the modular exponentiation (which conveniently is also required by RSA itself). The claim that it is necessarily O(k^{3}) is simply wrong. The Schönhage-Strassen algorithm can be used to implement modular exponentiation in O(k^{2}) log(k) log(log(k)))!

But the really sad part of this is that Peter Shor says exactly this in his paper.

Asymptotically, the best classical result for gate arrays for multiplication is the Schonhage–Strassen algorithm [Schonhage and Strassen 1971, Knuth 1981, Schonhage 1982]. This gives a gate array for integer multiplication that uses O(l log l log log l) gates to multiply two l-bit numbers. Thus, asymptotically, modular exponentiation requires O(l

^{2}log l log log l) time. Making this reversible would na¨ıvely cost the same amount in space; however, one can reuse the space used in the repeated squaring part of the algorithm, and thus reduce the amount of space needed to essentially that required for multiplying two l-bit numbers; one simple method for reducing this space (although not the most versatile one) will be given later in this section. Thus, modular exponentiation can be done in O(l^{2}log l log log l) time and O(l log l log log l) space.

While the Schonhage–Strassen algorithm is the best multiplication algorithm discovered to date for large l, it does not scale well for small l. For small numbers, the best gate arrays for multiplication essentially use elementary-school longhand multiplication in binary. This method requires O(l^{2}) time to multiply two l-bit numbers, and thus modular exponentiation requires O(l^{3}) time with this method. These gate arrays can be made reversible, however, using only O(l) space.

Does nobody read their references anymore?