Efficiently Factoring Integers

Integer Factorization ┬áis thought to belong to a class of problems known as NP-intermediate. This class lies between the easy P class (polynomial class) and the difficult NP-complete class. It is known as a trapdoor function which means it’s easy to compute in one direction, but very hard in the opposite direction… or so it seems.

Cellular automata are worlds with simple rules that can result with chaotic and complex behaviour. For example, rule 30. This pyramid is produced by following the 8 keys. The 3 colours at the top produce the cell below it – it is procedurally generated starting from the top and goes down.

What’s even more interesting is that some of these rule sets are Turing complete. This means given the right input (the right set of starting points), it can compute anything. What’s more is that some of the cellular automata are reversible, in that if you know the current state, you can compute the previous state. An example of this is rule 51, in which bits are flipped. Unfortunately this particular rule isn’t both Turing complete and reversible, which is what is desired. But what’s so important about combining these two things? Consider the following thought experiment.

Person A multiplies two large primes to get a semiprime (a number which has exactly 2 prime factors) and tells person asks person B what the semiprime is and asks him to figure out what two numbers he multiplied (i.e. to factor the semiprime). Person B is aware of the location and velocity of every atom in the universe. Trying to figure out what the 2 primes were in the traditional way would take exponential time, but were person B to simply compute the past by means of simulating the universe going backwards in time, it would only take as long as it took for A to multiply those two numbers (in terms of the complexity class given that reversing time for x seconds takes an amount of time proportional to this). In other words, by focusing on reversing time we can transform an exponentially difficult problem into a mere polynomially difficult problem.

Taking this idea and applying it in a practical way can be done as follows: design a computer inside a Turing complete reversible cellular automata that takes 2 numbers as input, tests that they are prime using the AKS primality test, sorts the numbers in ascending order then multiplies them and outputs the result. To factor a semiprime, you need only set the semiprime as the output and set it to go backwards in time, and the bits would flow back into the multiplying machine and 2 primes would form as if by magic.

Were this algorithm to work, it would not on its own prove that P=NP. Only producing an algorithm that is classed as NP-complete could do this. However this is an important step forward, as it would be the first algorithm that solved what was thought to be an NP-intermediate problem. An interesting fact is that if P != NP there must be at least one problem that belongs in the class NP-intermediate, so revealing that one of these problems actually belongs in P will lower the confidence that P != NP.

Though it still would be a significantly powerful algorithm to invent. If the totient function were vulnerable to be solved in the same way (and I suspect it is), it would become trivial to break RSA encryption. Meaning that you could hack into virtually any system online with ease. You would be able to easily acquire the log in details of any user, such as their Gmail account or their online banking account. Online banking systems would be totally insecure.

One seeming contradiction in all of this is that logic gates in computers are normally irreversible. NAND, XOR, OR gates all take 2 inputs and return 1 output. In an OR gate, the inputs (1, 1) and (1, 0) both produce (0), so how can a reversible machine magically know what input produced it? It can’t. This is why traditional logic gates cannot be used. Instead, a more advanced form of logic gates are used. These are known as Fredkin gates. Their special property is that the number of 1s and 0s in the input exactly matches the amount in the output – everything is conserved. These gates are Turing complete to can be used to do any arbitrary calculation.