20051227, 03:58  #1 
"William"
May 2003
New Haven
3×787 Posts 
Greg Childers finds Record P+1 Factor
The ElevenSmooth server was upgraded to version 2.6.3 at the end of November. This version handles P1 and P+1 as well as ECM. This paid off a few days later when Greg Childers found a 41 digit factor of M(6336) by P+1. This was a remarkable example of the extra factors sometimes found with the polynomial extensions. The largest factor of P+1 is 7.8 x 10^{22}, but the 41 digit divisor was found using the default B2 value of 2.2 x 10^{9}.
Only the tiny factor 63361 was previously known for the primitive part of 2^{3168}+1. This factor reduces the unfactored part from C574 to C534. The new factor is 11410838220690884611011414462190301943937 Last fiddled with by wblipp on 20051227 at 04:00 
20051227, 08:24  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Was this really found by P+1? First, p42 + 1 seems to have a 34 digit prime factor. Then, P1 is quite smooth. If P+1 uses the starting value s and s^22 is a quadratic residue, it'll work in a group isomorphic to Z/Zp, just like P1.
Alex Last fiddled with by akruppa on 20051227 at 14:38 Reason: 2, not 4 
20051227, 08:31  #3 
Sep 2002
1426_{8} Posts 
Whenever you all figure out if this is correct, if it is, I will post the news to the DC info "New News" section.

20051227, 11:35  #4 
Aug 2002
Buenos Aires, Argentina
10101001100_{2} Posts 
As Alex pointed above, p1 = 2 ^ 7 x 3 ^ 2 x 11 x 19 x 79 x
211 x 2833 x 75389 x 636553 x 667781 x 31317425413, so the p+1 run was only a slow way to perform p1. This is explained in the Mersennewiki. 
20051227, 13:54  #5  
"William"
May 2003
New Haven
3·787 Posts 
Quote:
I had noted that P1 was much more likely than P+1, but was suspecting a programming bug in the ecm server / ecm client chain rather than an algorithmic issue. The default polynomials for P+1 and P1 are different, and this factor is not found using B1=11M and the pm1 flag. It is found using the pp1 flag, which told me that there was no error in the ecm server / ecm client chain. Regardless, I'm pleased to have a new ElevenSmooth factor. 

20051227, 14:37  #6 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
P1 uses the x^S polynomial for degree>6 as we can use x^{S/2}+x^{S/2} for the cost of 3 extra multiplies per root instead. Afaik P+1 uses Dickson polynomials for degree>2. You could try with "pm1 dickson 60" to check if P1 finds the factor.
Alex 
20051227, 16:31  #7  
"William"
May 2003
New Haven
3×787 Posts 
Quote:
The P+1 report says it used dickson6, so I tried that first. When nether 6 nor 60 worked, I tried specifying B2 to match the higher default in P+1. The following all failed to find the factor: pm1 dickson 6 11000000 pm1 dickson 60 11000000 pm1 dickson 6 11000000 2254045320 I finally found the factor with pm1 dickson 60 11000000 2254045320 The third failure surprised me because that matched the P+1 run in both polynomial and B2 bounds. Should be concerned about the correctness of ECM6, or are there enough differences in the methods that this is not surprising? 

20051227, 17:23  #8 
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
For P+1, like for ECM, a group element X and its inverse produce the same root for the F and G polynomials, so the factor is found if there are two values u,v so that uX = (±v)X. For the BrentSuyama extension, this effectively doubles the degree, since (x+y)(xy) = x^2y^2, and similarly for Dickson polynomials. Try again with
pm1 dickson 12 11000000 2254045320 If that doesn't find it, I need to investigate further. Alex Last fiddled with by akruppa on 20051227 at 18:44 
20051227, 18:14  #9  
"William"
May 2003
New Haven
4471_{8} Posts 
Quote:


20051227, 20:18  #10  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Alex 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
M7508981 has at least 12 prime factors(new factor # record)  pdazzl  Factoring  261  20151109 15:00 
New P+1 record factor  akruppa  Factoring  5  20071101 16:47 
SOB Finds a big prime!  Prime95  Lounge  5  20070506 09:01 
Record ECM factor found  philmoore  Factoring  10  20050227 09:38 
Record ECM factor found by Prime95  philmoore  Lounge  0  20030624 20:41 