Transcript Lucas-Lehmer Primality Tester Presentation 1: Proposal

Lucas-Lehmer Primality Tester
Presentation 1: Proposal
Team:
Nathan Stohs
Joe Hurley
Brian Johnson
Marques Johnson
Applications, History
• Lucas-Lehmer is a test used to search for
Mersenne Primes.
• Mersenne Primes are primes of the form 2^p – 1
• Given p, will conclusively determine primality
after p-2 iterations of the algorithm.
• Computationally heavy, but numbers tested
independently, so easily distributable.
• Difficultly lies in choosing an implementation
www.mersenne.org
Applications, contd.
• A hardware implementation of this algorithm is
not going to save any lives. Why important then?
• Mersenne primes (found with this test) are the
largest prime numbers we know of today.
• A pool of over 70,000 computers currently run an
implementation of this algorithm, with aggregate
performance peaking at 14 Teraflops.
• This is not intended to be a commercial product.
www.mersenne.org/primenet/
Algorithm
• Somewhat basic.
•
• Mp is Prime iff
• Simple iterative structure, with p iterations
• Includes modulo, squaring, arithmetic
• Need for fast squaring
Design
• Are we going to be able to beat a 4 GHz
Pentium 4 implementing this algorithm in hand
optimized assembly using FFTs for squaring?
• No.
• However, it would use much less power
• Design is limited by the maximum value of p
which we want to test, due to squaring.
• Design scales quite nicely with max p
Flowchart
Squaring operation will dominate
the design in layout area
Approx 10k-15k transistors
Due to math constraints, will
not require full blown divison
Approx 4k-5k transistors
Check for 0 residue on last iteration
Arithmetic, registers, other controls
Approx 3k transistors
Problems
• Will never be able to test untested numbers, at
best an experiment for future work.
• A lot will depend on how we implement the
squaring, leading too..
• May be too easy! Backup plan is to use
FancyMath™ to aid performance and make the
project more “interesting”.
• Other ideas considered:
• Implementation of Blowfish Cipher