### 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.

If you believe the Van den Nest and Pavlidis papers, then why don’t you just immediately write a program for “factoring with the iPhone”? The CIA, the Chinese government, the Mafia, Goldmann Sachs and the Vatican would all pay you millions of dollars for it.

All the talk about data base integration, all the boring details about already existing open software packages that you are going to use, the silly term emulated quantum cryptography, all that seems mostly irrelevant to the basic plan of “factoring with the iphone”. It might give a potential investor a bad impression, like you are trying to impress him/her with irrelevant buzz words.

The ability to factor in classical polynomial is

a consequenceof our research process. We were (are) trying to build a database, had a search problem, now the goal is to classically emulate quantum systems so we can do quantum search in a classical environment. An implication of that is you can also do Shor’s.As for “just immediately write a program”, working on it — check back here for updates.

Cheers