The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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   

which has a lot of information about big primes.

-Ken "Dr." Math
Associated Topics:
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.