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
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
- Notice that I have removed the word "Large" from the title of this page. As I continue to research prime number theory it has become clear that a search for sixteen digit primes is trivial, at least compared to current searches which are in the thousands of digits!
- I have added a
refresh tag to this page so it automatically updates (current rate 60 seconds). You can change it if you want. For two minutes add
?time=120 to the end of the URL (time is in seconds).
- For reasons beyond my control the script factoring these numbers sometimes quits. I am currently working on another script that checks the status and restarts it if needed. Anyone interested in how I am doing this, and willing to give help and advice, is welcome to contact me.
- I finished the above mentioned script and now have it executing every twenty minutes, checking to see if the main script is still running, and of course re-starting it if it isn't. One of the interesting facets of getting this to work was figuring out how to log the current state of the script so that it can pick up from where it left off.
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.