View Single Post
Old 2009-09-24, 01:15   #9
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

111101111112 Posts
Post

Quote:
Originally Posted by Harvey563 View Post
I my opinion the very best reference for what you want to do is:

H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, Birkhäuser Boston, Boston, MA, 1994. ISBN 0-8176-3743-5.

It is clear. There are lots of examples in Pascal. And it is all about prime proving and factoring.

I will check that out. Thanks.

I decided to start reading here, under "Trial Factoring".

http://www.mersenne.org/various/math.php

Quote:
The next step is to eliminate exponents by finding a small factor. There are very efficient algorithms for determining if a number divides 2P-1. For example, let's see if 47 divides 223-1. Convert the exponent 23 to binary, you get 10111. Starting with 1, repeatedly square, remove the top bit of the exponent and if 1 multiply squared value by 2, then compute the remainder upon division by 47.
Remove Optional
Square top bit mul by 2 mod 47
------------ ------- ------------- ------
1*1 = 1 1 0111 1*2 = 2 2
2*2 = 4 0 111 no 4
4*4 = 16 1 11 16*2 = 32 32
32*32 = 1024 1 1 1024*2 = 2048 27
27*27 = 729 1 729*2 = 1458 1
Thus, 223 = 1 mod 47. Subtract 1 from both sides. 223-1 = 0 mod 47. Since we've shown that 47 is a factor, 223-1 is not prime.
In the example above, the author tests 223 - 1 to see if it will divide by 47. Taking 1 away from both sides, he ends up with zero, meaning not prime.

Below is a variation of that same procedure I tried in Excel. What I did was to take the same value and place it on both sides. 479 and 1087 are prime numbers. Not Mersenne. 893 is not prime.

The spacing went to crap! Down the left side is the binary string as shown across the top. An "x" appears on the same rows as a binary "0" to indicate the multiply-by-2 is not done. The last number of each row is the Modulo.

Quote:
479 111011111 Mod

1 - 1 2 2
1 - 4 8 8
1 - 64 128 128
0 - 16384 x 98
1 - 9604 19208 48
1 - 2304 4608 297
1 - 88209 176418 146
1 - 21316 42632 1


893 1101111101 Mod

1 - 1 2 2
1 - 4 8 8
0 - 64 x 64
1 - 4096 8192 155
1 - 24025 48050 721
1 - 519841 1039682 230
1 - 52900 105800 426
1 - 181476 362952 394
0 - 155236 x 747
1 - 558009 1116018 661


1087 10000111111 Mod

1 - 1 2 2
0 - 4 x 4
0 - 16 x 16
0 - 256 x 256
0 - 65536 x 316
1 - 99856 199712 791
1 - 625681 1251362 225
1 - 50625 101250 159
1 - 25281 50562 560
1 - 313600 627200 1
1 - - -
In the first and third test, on known primes, I ended up with one. Remove that from the right, as in the left, and I have zero. The center example ends at 661. The GCD of 893 and 661 is 1.

I wasn't expecting this type of result. I assumed anything on the GIMPS site would be exclusive to multiples of two. The strange part is, I can make this work in Excel, but not in code.

storm5510 is offline   Reply With Quote