mersenneforum.org  

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

Reply
 
Thread Tools
Old 2010-05-31, 11:13   #1
kurtulmehtap
 
Sep 2009

22·32 Posts
Default GIMPS factorization proof

Dear All,
Where can I find the proof and a little more detail of the Trial factoring algorithm described at the GIMPS Math page:
http://www.mersenne.org/various/math.php

Thanks
kurtulmehtap is offline   Reply With Quote
Old 2010-05-31, 11:39   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

I'm pretty sure the trial factoring algorithm is really just computing 2^23 mod 47. If it's 1, then 2^23-1=0 mod 47, which means that 47 divides 2^23-1.
These Wikipedia articles have more general info on the subject:
http://en.wikipedia.org/wiki/Exponentiation_by_squaring
http://en.wikipedia.org/wiki/Modular_exponentiation
Specifically, it looks just like the algorithm under Exponentiation by squaring's Underlying idea section, but with the addition of the modulo step.
Mini-Geek is offline   Reply With Quote
Old 2010-05-31, 15:00   #3
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52×17 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I'm pretty sure the trial factoring algorithm is really just computing 2^23 mod 47. If it's 1, then 2^23-1=0 mod 47, which means that 47 divides 2^23-1.
Nope. Its rather more sofisticated than that. See:

http://www.mersenne.org/various/math.php
lfm is offline   Reply With Quote
Old 2010-05-31, 15:30   #4
kurtulmehtap
 
Sep 2009

2416 Posts
Default

Quote:
Originally Posted by lfm View Post
Nope. Its rather more sofisticated than that. See:

http://www.mersenne.org/various/math.php
Thats the site I referred. I need the algorithm in detail.
Thanks
kurtulmehtap is offline   Reply With Quote
Old 2010-05-31, 15:39   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by lfm View Post
Since the OP started with that same link, it would be useful to explain what you meant by referring to what's beyond Mini-Geek's summary of the modular exponentiation.

Were you referring to the rest of the TF algorithm loop (to which the "The Math" page refers but does not explain very straightforwardly)? Perhaps that's what the OP is asking about.

Last fiddled with by cheesehead on 2010-05-31 at 15:40
cheesehead is offline   Reply With Quote
Old 2010-06-01, 04:53   #6
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52·17 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I'm pretty sure the trial factoring algorithm is really just computing 2^23 mod 47. If it's 1, then 2^23-1=0 mod 47, which means that 47 divides 2^23-1.
OK, it does that but to decide to check q=47 or not it searches thru the numbers of the form 2kp+1 (where p=23) for k starting at 1 so 47 happens to be the very first one checked. It also checks that 47 is 1 or 7 mod 8 ( it is 7) and that 47 is prime. Then it does the algorithm to check divisibility. Note it never has to actually compute 2^23 nor store 2^23 bits. It all works with normal 32 or 64 bit integers. Much of the checking can be does with a sieve.

Does that help?
lfm is offline   Reply With Quote
Old 2010-06-01, 13:24   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by lfm View Post
OK, it does that but to decide to check q=47 or not it searches thru the numbers of the form 2kp+1 (where p=23) for k starting at 1...
I knew that already, and I think the OP did, too (if not, it must've been due to a not-detailed-enough reading, as the page links to a proof of that part). I was referring to this part, i.e. the actual calculation once you've got the number you're going to divide:
Quote:
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.

Code:
                  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.
Mini-Geek is offline   Reply With Quote
Old 2010-06-01, 14:08   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I'm pretty sure the trial factoring algorithm is really just computing 2^23 mod 47. If it's 1, then 2^23-1=0 mod 47, which means that 47 divides 2^23-1.
.

I would hope that it ISN'T doing this particular computation.

Hint: There is no need to do it, since we have a THEOREM that tells
us when 2p+1 divides 2^p - 1.

The computation is not necessary.
R.D. Silverman is offline   Reply With Quote
Old 2010-06-01, 16:30   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I would hope that it ISN'T doing this particular computation.

Hint: There is no need to do it, since we have a THEOREM that tells
us when 2p+1 divides 2^p - 1.

The computation is not necessary.
However simple this theorem is, it would be daft
to bother to include it in a TF program.

David
davieddy is offline   Reply With Quote
Old 2010-06-02, 08:54   #10
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

1A916 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I knew that already, and I think the OP did, too (if not, it must've been due to a not-detailed-enough reading, as the page links to a proof of that part). I was referring to this part, i.e. the actual calculation once you've got the number you're going to divide:
ya, ok its a well known algorithm for calculating x^y mod z without calculating x^y. eg one implementation in the GMP library is called mpz_powm()
lfm is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
APR-CL as primality proof f1pokerspeed FactorDB 14 2014-01-09 21:06
...another proof down the drain? Batalov Math 1 2008-08-12 19:02
help with a proof vtai Math 12 2007-06-28 15:34
Proof (?!) that RH is false? bdodson Lounge 6 2007-03-19 17:19
A Second Proof of FLT? jinydu Math 5 2005-05-21 16:52

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

Wed Feb 24 18:49:44 UTC 2021 up 83 days, 15:01, 0 users, load averages: 2.24, 2.09, 1.97

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.