Multiplication

Since so much of modern cryptography is based on the complexity of factoring primes, few theoretical math results could have as immediate and devastating effect as a polynomial solution to factoring. Factoring has not been proven as NP-complete. However, it is NP-easy meaning that if it turns out P=NP this little program could cause widespread devastation.

In our example we factor the number 9. To do this we set up the board similar to how multiplication for an ALU would be set up. All numbers are represented in binary and simple multiplication (single binary number from bottom row * top row) and addition are performed using Opt simultaneously. As can be seen in the solution file, 9 (1001) factors to 3 (011) and 3 (011).

source | solution