mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Closed Thread
 
Thread Tools
Old 2004-01-22, 18:55   #1
benmichaelx
 

32028 Posts
Lightbulb question about the algo

I'm not the greatest mathamatitian (Ok, I'm lucky I can add 2+2). But I've been watching prime 95 working hard on my machine the last few months going thru what I believe to be n-1 iterations for the possible prime n.

Now why does it have to go thru all those iterations? My thinking is a number (non-prime) can only be divisible by a number that is half itself or less. For example the number 12. It is divisible by numbers less than or equal to half of 12 in otherwords less than or equal to the number 6. 1,2,3,4 and 6. Is this true for all numbers? So to test if something is prime could we stop once we've reached the halfway point.

I realize this may be obviously wrong or right to all of you geniuses out there but ... I was just thinking.

Ben
 
Old 2004-01-22, 19:07   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010110000112 Posts
Default

The algorithm you showed is time-consuming and not so efficient as Lucas-Lehmer test.

If you are interested in algorithms, try this link:

http://www.mersenne.org/math.htm

Luigi
ET_ is offline  
Old 2004-01-22, 23:05   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

The Lucas-Lehmer algorithm isn't trying to find factors, that is what the earlier elimination tests trial factoring and p-1 factoring do.

LL works as follows (from the prime95.chm help file)
For example, to prove 2^7 - 1 is prime:
( 2^7 - 1 = 128 - 1 = 127 )
With the exponent 7 there are 7 - 2 iterations.
Always start with S(0) = 4,
square, subtract two, mod by the mersenne number,
use the remainder as the starting value for the next iteration.

S (0) = 4
S (1) = 4 * 4 - 2 mod 127 = 14
S (2) = 14 * 14 - 2 mod 127 = 67
S (3) = 67 * 67 - 2 mod 127 = 42
S (4) = 42 * 42 - 2 mod 127 = 111
S (5) = 111 * 111 - 2 mod 127 = 0

Only if the result of the last iteration is 0 is it a mersenne prime.

Using a special math technique (dwt) prime95 doesn't actually do the mods.

Trial factoring is a specialized version of the algorithm you described.
The mersenne numbers that are being tested are very large
so instead of testing to half ( really only to the square root is sufficient )
the factors tested are numbers (maximum) that can fit in upto 72 bits, depending on the size of the mersenne exponent ( smaller exponents go to a smaller number of bits ). 72 bits can hold a 22 digit number ( factor ).

Each factor ( q ) is in the form 2kp + 1, with each k a positive integer.
Example for 2^17 - 1, if trial factoring the factors tested would be
2*1*17 + 1 = 35, 2*2*17 + 1 = 69, 2*3*17 + 1 = 103, 2*4*17 + 1 = 137
2*5*17 + 1 = 171, ... 2*10*17 + 1 = 341
any bigger would be above the integer square root of 131071 = 362
( 2^17 - 1 = 131071 )
dsouza123 is offline  
Old 2004-01-23, 12:36   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by benmichaelx
I've been watching prime 95 working hard on my machine the last few months going thru what I believe to be n-1 iterations for the possible prime n.
The numbers Prime95 tests are of the form 2[b]n[/b]-1 -- that is, 2 raised to the power of n, minus 1. For example, 25 - 1 = (2 x 2 x 2 x 2 x 2) - 1 = 31.

It can be proven that if n is not a prime, then 2[b]n[/b]-1 is also not a prime. So when we're looking for 2[b]n[/b]-1 that is prime, we consider only the cases where n itself is a prime. We often write 2[b]n[/b]-1 as 2[b]p[/b]-1 to remind ourselves that we are looking only at the cases where the exponent (n or p) is a prime. The fact that there are two different primes involved -- p and {we hope this is prime} 2[b]p[/b]-1 -- can sometimes be confusing.

Suppose the number that Prime95 is testing is 220996011-1. The exponent, 20996011, has only eight decimal digits. But the tested number, 220996011-1, has over six million decimal digits. To test this number, Prime95 must perform only 20996010 iterations, not 220996011-1 iterations.

Quote:
Now why does it have to go thru all those iterations?
Well, 20996011 iterations is a lot, but it's far, far less than 220996011-1 iterations. 20996011 iterations takes several weeks. 220996011-1 iterations would take much, much longer than the age of the universe!
cheesehead is offline  
Closed Thread

Thread Tools


All times are UTC. The time now is 18:38.

Sun Mar 7 18:38:26 UTC 2021 up 94 days, 14:49, 1 user, load averages: 2.02, 1.71, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.