Prime Number Search

This is the stats page for a Python script (currently running on this server) that is brute force factoring out sixteen-digit prime numbers from combinations of select eight-digit prime numbers.

Last prime found
2953291717412371

The last number checked [#79421 of 231361] factored in 54329278 calculations in 33m:9s

Started on Wed Nov 9 23:54:09 2005
2555177423908 total calculations to date (34.6710162906% done)

The results are written to two files primes16.txt and unprimes16.txt

News & Notes

So what's so big about big numbers?

Large prime numbers are important to cryptography. When used as encryption keys the time it takes to search for the prime number being used as a key (by factoring. There is only one factor for a prime number, the number it's self) makes decryption prohitively long.

My personal interest in prime numbers however stems from a different application and this project, the search for sixteen-digit squares, is a curious outgrowth of that.

I have been recently working with the 'vonNeumann Inner Square' algorithm, which is a psuedo-random number generator. This algoritm requires eight-digit "seed" numbers and so I decided that, instead of generating them at random, it might be more productive to start with prime numbers, which started me on a search for eight-digit primes.
I decided not to check every possible eight digit number but instead only certain ones, and so to start I took the first twenty two-digit primes 13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 and combined them into four digit numbers ('1317', '1319', etc.). Although I knew that not all these numbers would be prime I suspected that some of them (being based on two-digit primes to start with) had a higher probibility of being prime and thus would limit the 'search space'. So I then checked each of the 484 (222) four-digit pairs for "primeness" to come up with a select set of seventy two four-digit primes.
Having done this it was time to combine these four-digit pairs into eight-digit pairs for a total of 5184 numbers (or 722). Again obviously not all of these are prime numbers and so I started checking each one for "primeness".
To do this I wrote a Python script that did a "brute force" factoring of each number: the number/2, number/3, number/4, etc. However I quickly realized that, because these are eight-digit numbers (in the 10,000,000th place) it would take tens-of-thousands of calculations per number to check each, especially if it's a prime... and there were 5148 numbers to check!
Fortunately I happened to have a "spare" computer on hand and so set it to the task...
...and as of this writing (11-6-05) it has been three weeks... and it is still only in the 29,000,000 set of numbers!

In the mean time I started investigating optimized algoritms for factoing prime numbers.
There is a lot of research going on in this field and I found some interesting equations and code... unfortunately all beyond my math and programming skills.
However I did learn about the maximum number to search for (the square root) and a better way to work through the search space (from the middle, towards the ends) and so incorporated these ideas into a new algorithm.