Prime Number Information
Date: 15 Apr 1995 08:47:13 -0400 From: Andy Cook Subject: Prime numbers Prime numbers fascinate me, but information about them is hard to find. Could you please tell me; 1) What is the largest prime number that has been discovered? 2) Who found it? and when? 3) What are the theories that are used when searching for prime numbers? 4) What is the formula? :-) 5) What is the connection between prime numbers and encryption? Hope this isn't question overload. If you can answer any of these or steer me to someone who can, I'll be very appreciative. Thank you for your time. Andy Cook
Date: 15 Apr 1995 17:02:16 -0400 From: Dr. Ken Subject: Re: Prime numbers Hello there! 1) The largest prime number known is 2^859433 - 1. 2) I believe it was discovered and verified by Cray Research in 1994. 3) Basically, you have to look at specific forms that prime numbers can take, rather than just looking at big numbers and trying to factor them. Prime numbers of the form 2^n - 1 are called Mersenne primes, named for Marin Mersenne, who was one of the folks interested in them back in the 1640's. We know this about them: (a) in order for 2^n - 1 to be prime, n has to also be prime. (b) If n is prime, then 2^n - 1 is only divisible by primes of the form 2*k*n + 1 if it's divisible at all. So you can see that instead of having to go through and check our number 2^859433 - 1 for divisibility by all primes, we only have to check divisibility by 2*1*859433 + 1 = 1718867 2*2*859433 + 1 = 3437733 and so on. Note that these numbers also have to be prime, so we can check their primality first before trying to divide them into 2^859433 - 1. 4) There can be no polynomial formula in n that will give you all primes as a function of n. Basically, we've been reduced to using a lot of these special cases of primes to see whether we can figure out some big primes. 5) Briefly, here's how it works. You have a really big number that's the product of two big primes. Since it's really hard to factor numbers when they're big (yes, even for a computer), you can tell people what the big number is, but you don't tell them what its factors are. Then people use the big number to encode a message, and you need to know the factors to decode it. (I admit I'm a little fuzzy on exactly how this works, since someone is borrowing my number theory book) If you want more information on primes and you can access the World Wide Web, check out http://www.utm.edu/departments/math/largest.html which has a lot of information about big primes. -Ken "Dr." Math
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.