mersenneforum.org Greg Childers finds Record P+1 Factor
 Register FAQ Search Today's Posts Mark Forums Read

 2005-12-27, 03:58 #1 wblipp     "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 P-1 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 1022, but the 41 digit divisor was found using the default B2 value of 2.2 x 109. Only the tiny factor 63361 was previously known for the primitive part of 23168+1. This factor reduces the unfactored part from C574 to C534. The new factor is 11410838220690884611011414462190301943937 Last fiddled with by wblipp on 2005-12-27 at 04:00
 2005-12-27, 08:24 #2 akruppa     "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, P-1 is quite smooth. If P+1 uses the starting value s and s^2-2 is a quadratic residue, it'll work in a group isomorphic to Z/Zp, just like P-1. Alex Last fiddled with by akruppa on 2005-12-27 at 14:38 Reason: -2, not -4
 2005-12-27, 08:31 #3 Jwb52z     Sep 2002 14268 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.
 2005-12-27, 11:35 #4 alpertron     Aug 2002 Buenos Aires, Argentina 101010011002 Posts As Alex pointed above, p-1 = 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 p-1. This is explained in the Mersennewiki.
2005-12-27, 13:54   #5
wblipp

"William"
May 2003
New Haven

3·787 Posts

Quote:
 Originally Posted by akruppa Was this really found by P+1? First, p42 + 1 seems to have a 34 digit prime factor. Then, P-1 is quite smooth. If P+1 uses the starting value s and s^2-4 is a quadratic residue, it'll work in a group isomorphic to Z/Zp, just like P-1.
Is gmp-ecm6 clever enough to figure this out after the factorization has completed? That would explain why it reports the factor was found with P-1 even though the -pp1 flag was used.

I had noted that P-1 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 P-1 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.

 2005-12-27, 14:37 #6 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts P-1 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 P-1 finds the factor. Alex
2005-12-27, 16:31   #7
wblipp

"William"
May 2003
New Haven

3×787 Posts

Quote:
 Originally Posted by akruppa You could try with "-pm1 -dickson 60"
I expected you to say that ECM6's report of [factor found by P-1] was definitive proof, or perhaps that we could use the reported x0 value of 1012347747 to check for quadratic residue.

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?

 2005-12-27, 17:23 #8 akruppa     "Nancy" Aug 2002 Alexandria 46438 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 Brent-Suyama extension, this effectively doubles the degree, since (x+y)(x-y) = x^2-y^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 2005-12-27 at 18:44
2005-12-27, 18:14   #9
wblipp

"William"
May 2003
New Haven

44718 Posts

Quote:
 Originally Posted by akruppa Try again with -pm1 -dickson 12 11000000 2254045320
That finds the factor.

2005-12-27, 20:18   #10
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by wblipp Is gmp-ecm6 clever enough to figure this out after the factorization has completed? That would explain why it reports the factor was found with P-1 even though the -pp1 flag was used.
Sorry, hadn't answered that yet. Yes, when a prime factor p is found by P+1, GMP-ECM checks the quadratic character of s^2-2 (mod p) and prints the "found by P-1" message if it is a quadratic residue.

Alex

 Similar Threads Thread Thread Starter Forum Replies Last Post pdazzl Factoring 261 2015-11-09 15:00 akruppa Factoring 5 2007-11-01 16:47 Prime95 Lounge 5 2007-05-06 09:01 philmoore Factoring 10 2005-02-27 09:38 philmoore Lounge 0 2003-06-24 20:41

All times are UTC. The time now is 13:23.

Fri May 14 13:23:18 UTC 2021 up 36 days, 8:04, 0 users, load averages: 1.58, 1.73, 1.90