Detecting PrimesQuick Number Theory ReviewApplication of PrimesAlgorithmsSieve of EratosthenesFermat’s TheoremRabin-Miller TestRabin-Miller Test (cont.)Slide 9Special PrimesMersenne PrimesHomework QuestionsReferencesDetecting PrimesAdam BrooksCOT4810February 12, 2008Quick Number Theory ReviewPrime numberA natural number > 1 which has exactly two divisors – 1 and itselfComposite numberA non-prime number… a natural number that has a positive factor other than 1 and itselfApplication of PrimesComputer Science applies prime numbers in:CryptographyHashing schemesSorting schemesRandom number generationAlgorithmsNumerous algorithms exist for detecting if a given number is prime or composite.Finding primes vs. testing if a number is primeDeterministic tests vs. Probabilistic (Monte-Carlo) testsSieve of EratosthenesAncient Greek algorithm for identifying primes from 2..nSteps:Start with 2 and strike-out all multiples in the listThe first remaining number (3) is prime, strike-out it’s multiples and repeat the processFermat’s TheoremProbabilistic test to determine if a number n is prime.Repeated k times for randomly selected integers in the range [1, n)If the equality an-1 mod n = 1 fails, then a is said to be a witness for the compositeness of n.Rabin-Miller Test Probabilistic (normally) method similar to Fermat’s where “witnesses” to a number’s compositeness are identifiedA witness would be any integer w satisfying the following two conditions:1. wn-1 = 1 mod n, or2. For some integer k, and 1 < gcd(wn – 1, n) < nknm21Rabin-Miller Test (cont.)A simple algorithm can be outlined:1. Input prime candidate n2. Select m integers w1, w2, …, wm at random from the set {2, 3, …, n – 1}3. For i = 1, 2, …, m, test whether wi is a witness4. If none of the m integers are witnesses output yes, else, output no.Rabin-Miller Test (cont.)How accurate is it?Rabin theorized that if n is composite, more than half the numbers in the set {2, 3, …, n – 1} are witnesses to the compositeness of n.The probability of n being prime if the algorithm returns yes is:Where m is the number of random integers selected to test as witnesses.m)21(1Special PrimesProbabilistic algorithms are useful in the search for primes due to the large numbers of computations required to find them…GIMPS (Great Internet Mersenne Prime Search) is a Distributed Computing project supporting the search for Mersenne primes – of the form 2p – 1.The largest known prime is traditionally a Mersenne prime.Mersenne PrimesThe current largest prime (found in Sept. 2006) is the 44th known Mersenne prime, 232,582,657 – 1 and is 9,808,358 digits long. mersenne.org and the EFF currently offer prizes for finding the largest primes ($100,000 for the first 10,000,000 digit prime)The bad news:Testing a single 10,000,000+ digit number takes two months on a 2GHz P4Homework Questions1. What form do Mersenne primes take?2. Give two uses for prime numbers in computer science applications.ReferencesDewdney, A.K. The New Turing Omnibus. pp 335-338.Rabin, Michael O. “Probabilistic algorithm for testing primality.” Journal of Number Theory, volume 12, issue 1. February, 1980. pp 128-138.GIMPS – The Great Internet Mersenne Prime Search. http://www.mersenne.orgBernstein, D.J. Distinguishing prime numbers from composite numbers: the state of the art in 2004. http://cr.yp.to/primetests.htmlPrime Numbers.
View Full Document
Unlocking...