Assumptions (tsk tsk)

by noospheer

Human beings like to make assumptions. Assumptions seem to make the world a less demanding place to understand. Ironically, no kind of human is more susceptible to falling prey to assumptions than the scientist. In the strict definition, a scientist prides him/herself on proof through rigorous observation of well-constructed experiments.

However, if a question is hard, it’s difficult to devise an experiment which can answer it. When this is the case, many scientists fall back on beliefs which they assume to be true. This is unfortunate, as the universe is mysterious, and assumptions generally turn out to be false (ex: “all heavenly bodies orbit the Earth”).

A modern scientific assumption is that factoring is hard. Factoring involves taking a number and determining which two prime numbers multiply together to equal the original number. For example, 21 factors into 3 times 7. Despite the simplicity of the problem, there is no obviously efficient way to solve it. So, if the original number is sufficiently large, a computer may take a billion years to get the answer. Due to its hardness, factorization is at the heart of public key cryptography (PKC).

PKC is responsible for keeping computer systems secure. Virtually all institutions encrypt data with PKC. Virtually all ‘secure’ online transactions and digital signatures rely on PKC for their relative security. Symmetric-key cryptography (SKC – using a secret key that cannot be guessed logically) doesn’t directly rely on PKC, but the problem with SKC keys is a critical requirement that they be shared by both parties. This implies a secure connection must be established in order to share the private key in the first place — unless you share the key off-network. Simply, SKC needs factoring to be hard too.

Shor’s quantum algorithm factors in polynomial time (fast). Thus, Shor’s discovery ruins current security systems. However, it is a quantum algorithm and requires a quantum computer. Recently, Shor’s algorithm was implemented on a quantum computer and succeeded in factoring the number 21 in polynomial time. However, PKC uses numbers much larger than 21. So, it would be interesting to see whether Shor’s algorithm can be efficiently implemented on a classical computer, such as an iPhone.

It is proven here and extended here, that at least one major component of Shor’s factorization algorithm – the quantum Fourier transform (QFT) – can run efficiently on classical computers. The harder part of Shor’s is something called modular exponentiation (ME), and this is commonly assumed to be an impossible task for classical computers. However, it is also now proven that ME can be broken down and reconstructed in terms of the QFT. Therefore, the totality of Shor’s algorithm can run on an iPhone. If you find this alarming, rest assured such a breakthrough brings QKD much closer to fruition.

There are deep subtleties in the papers cited above, which we are carefully investigating. Should our assumption that factoring is classically easy prove true, we will publish our findings here.