A distributed approach to proving large numbers prime
Thomas William Valente · 1992
The problem of testing a given number for primality was known to the school of Pythagoras in ancient Greece, where Euclid proved there are infinitely many primes. In recent years, this problem has gained renewed interest as has the companion problem of factoring integers into primes, due in large part to their application to the area of cryptography. As a result, new and reasonably fast primality tests have been devised, many of which will produce a certificate of primality for its input which can then be verified in polynomial time in the length of the input. Of these tests, the most successful in practice has been an elliptic curve primality prover first described by Oliver Atkin (1986) and first implemented by Francois Morain (1988). In this thesis, we give a historical background to primality testing, and describe Atkin's test, including the underlying mathematical theory. We then discuss our first improvements, namely the use of reduced class equations in Atkin's test, and the transformations needed to map roots of these equations to the roots of the so-called genuine equations. Finally, we turn our attention to the issue of distributing the Atkin test across a network of workstations. In doing so, we describe a system for distributed computation and, with it, we demonstrate: (1) the benefits of distributing Atkin's test as a function of the length of the input; (2) the ability to prove so-called titanic numbers (having 1000 or more digits) prime; (3) the potential of our distributed approach, given a large number of workstations.