How Do the Big Boys Find Primes

So we have seen my program now, but what computer programs do the mathematicians use to find ever larger prime numbers? The two most popular right now are the Quadratic Field Sieve and the Number Field Sieve. The Number Field sieve being the most popular of the two.

Prime numbers are needed not only in the, lets find a new million digit worthless prime number that will satisfy my craving for math way, but also for industrial uses regarding encryption. But usually in this 'industrial' use for prime numbers, the numbers need not be prime, they just must have a low probabality of being prime, about 1 x 10-24 percent chance of being composite. These (strong) probable primality tests can be combined to show the probabality of being composite is very low for numbers less than 340,000,000,000,000. Again, for RSA encryption, this is enough.

But that isn't all that interesting, at least not to me. No the interesting thing is proving primality for numbers that are hundreds of thousands to millions of digits long (If you don't think so, just nod your head and smile). But you may ask, how do you prove the primality of a number so large? Obviously a division algorithm like I used in my QB program wouldn't do the trick. We could have all the computers on Earth working on a number that large for longer than the universe has been in existance and still not know whether or not the number is prime or not. The way we (I should say they, since I haven't done anything important with respect to primes) actually prove primality is using tests. This obviously the better way to prove primality, since we deal with the properties of primes (certain types anyway) rather than just dividing.

The first theorem we will deal with is the Lucas-Lehmer Test:

Theorem:

Let n>1. If for every prime factor q of n-1 there is an integer a such that

then n is prime.

Proof:

http://www.utm.edu/research/primes/prove3.html

To show n is prime we need only show that f(n) = n-1 (f(n) is Euler totient function), or more simply n-1 divides f(n). Suppose that this is not the case, then there is a prime q and exponent r>0 such that qr divides n-1, but not f(n). For this prime q we must have an integer a that satisfies the conditions above. Now let m be the order of a modulo n, then m divides n-1 (first condition), but not (n-1)/q (second condition). So qr divides m which divides f(n) - a contradiction which proves the theorem.

Now if you read over that, and didn't have a clue what was going on, don't feel alone, neither did I. But here, I did a little research for us, and this is what I came up with. Eulers totient function, f(n), is this:

f(n) is defined to be the number of positive integers not greater than n and relatively prime to n. For example, if p and q are distinct primes and r and s are positive integers, then

f(pr)=pr-1(p-1)

f(prqs)=pr-1qs-1(p-1)(s-1)

http://www.mathsoft.com/asolve/constant/totient/totient.html

Now lets deal with Proth's Theorem:

Theorem:

Let n = h2k+1 with 2k > h. If there is an integer a such that a(n-1)/2=-1 (mod n), then n is prime.

Proof:

I am working on this one, but since I'm just a 17 year old dude, this is taking me some time, but if you have a proof of this theorem, I would love it if you could send it to me. THANKS!

Mail: Jeromeyers@hotmail.com

Ok, so those are a few theorems, but a really good place to go is http://www.utm.edu/research/primes/ they tell you all you need to know, although the math is quite dense, I guess that is what you get when you research a topic that is being studied by the worlds top mathematicans.

[PREVIOUS][NEXT]