20100531, 11:13  #1 
Sep 2009
2^{2}·3^{2} Posts 
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 
20100531, 11:39  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
I'm pretty sure the trial factoring algorithm is really just computing 2^23 mod 47. If it's 1, then 2^231=0 mod 47, which means that 47 divides 2^231.
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. 
20100531, 15:00  #3  
Jul 2006
Calgary
5^{2}×17 Posts 
Quote:
http://www.mersenne.org/various/math.php 

20100531, 15:30  #4  
Sep 2009
24_{16} Posts 
Quote:
Thanks 

20100531, 15:39  #5  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
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 20100531 at 15:40 

20100601, 04:53  #6  
Jul 2006
Calgary
5^{2}·17 Posts 
Quote:
Does that help? 

20100601, 13:24  #7  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Quote:
Quote:


20100601, 14:08  #8  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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. 

20100601, 16:30  #9  
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
Quote:
to bother to include it in a TF program. David 

20100602, 08:54  #10  
Jul 2006
Calgary
1A9_{16} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
APRCL as primality proof  f1pokerspeed  FactorDB  14  20140109 21:06 
...another proof down the drain?  Batalov  Math  1  20080812 19:02 
help with a proof  vtai  Math  12  20070628 15:34 
Proof (?!) that RH is false?  bdodson  Lounge  6  20070319 17:19 
A Second Proof of FLT?  jinydu  Math  5  20050521 16:52 