I had an opportunity to review an old post I had written about playing with prime numbers. In it, I wrote out an explicit formula for a number, expressed as a product of primes. This goes to the definition of a composite or a prime number.

Whats interesting is what leaps out at you when you look at something you wrote a while ago.

Looking at the formula I wrote down, there is a very easy way to define if a number is prime or composite.

For the e(i) ∈ {Integers}, a number is prime if ∑_{i = 1 .. ∞} e(i) = 1. It is composite if ∑_{i = 1 .. ∞} e(i) > 1.

All you need are the e(i) signatures of the number. And technically speaking, you only have to search them up to φ_{i} > √N + 1. Which if you think about it, is an embarrassingly parallel factorization problem.

Shor’s algorithm it isn’t. But I might see if I can do some quick MPI (or even better, Julia!!) bits with this to try this very very big integers. See how it performs …

Yeah, I know, I am supposed to be writing my talk. Working on that too …