Abstract: The quest to discover a new largest known prime has been ongoing for centuries. Those seeking to break the record for the largest known prime have pushed the bounds of computing. We have come a long way since the 1970s when the instructor, Landon Noll, as a high school student discovered a 6533-digit prime. Today’s largest known prime is almost 25 million digits long! Those seeking to break the record for the largest known prime have pushed the bounds of computing. The development of these extreme primality testing programs offers important lessons today for those who must write code which must work correctly, even in the face of hardware errors, from the very first implementation.
To encourage the discovery of ever-larger primes, awards of $150000 and $250000 are offered to the first published proof of a discovery of a prime of at least 100 million and 1 billion digits respectively. The search for the largest known prime requires writing and running code that must run to completion, without any errors, throughout the entire proof of primality! A significant quality effort is required to write 100% error-free code. The calculations required to test extremely large numbers for primality must be fault resilient. One must overcome compiler and assembler errors, errors introduced by the kernel, and hardware errors such as memory errors and CPU calculation errors. The world record goes neither to the fastest coder nor to the person with the fastest hardware but rather to the first result that is proven to be correct. The reason for such extreme programming is that the length of the calculations exceeds the mean time to error of the calculating system. The motivation for such extreme care lies in the fact that a slow and correct answer is infinitely preferable to a fast but incorrect answer.
In this tutorial you will learn about the state of the art of searching for and proving the primality of very large numbers. How are these large primes discovered? What are some of the best ways to find a new world record-sized prime number? These and other prime questions will be explored. We will examine software and hardware-based approaches and will look at code fragments and hardware machine state diagrams.
