CERN Accelerating science

Computational challenges of finding the largest prime

Wednesday, 9 March, 2016 - 16:00 to 17:00

The quest to discover a new largest known prime has been on going 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 1978 when Landon's record breaking 6533-digit prime was discovered. Today’s largest known prime is almost 13 million digits long! 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. Because it takes a very long time to run to completion (several thousand hours in many cases), the code MUST RUN CORRECTLY the very first time! A significant QA effort is required to write 100% error-free code. Moreover considerable effort must be put into fault tolerant coding and recovery from the eventual operating system and hardware errors that will arise. The 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.

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.