mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > ElevenSmooth

 
 
Thread Tools
Old 2005-12-27, 03:58   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001001110012 Posts
Default 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
wblipp is offline  
Old 2005-12-27, 08:24   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline  
Old 2005-12-27, 08:31   #3
Jwb52z
 
Jwb52z's Avatar
 
Sep 2002

22·197 Posts
Default

Whenever you all figure out if this is correct, if it is, I will post the news to the DC info "New News" section.
Jwb52z is offline  
Old 2005-12-27, 11:35   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×337 Posts
Default

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.
alpertron is offline  
Old 2005-12-27, 13:54   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default

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.
wblipp is offline  
Old 2005-12-27, 14:37   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline  
Old 2005-12-27, 16:31   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default

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?
wblipp is offline  
Old 2005-12-27, 17:23   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline  
Old 2005-12-27, 18:14   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

Quote:
Originally Posted by akruppa
Try again with
-pm1 -dickson 12 11000000 2254045320
That finds the factor.
wblipp is offline  
Old 2005-12-27, 20:18   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
M7508981 has at least 12 prime factors(new factor # record) pdazzl Factoring 261 2015-11-09 15:00
New P+1 record factor akruppa Factoring 5 2007-11-01 16:47
SOB Finds a big prime! Prime95 Lounge 5 2007-05-06 09:01
Record ECM factor found philmoore Factoring 10 2005-02-27 09:38
Record ECM factor found by Prime95 philmoore Lounge 0 2003-06-24 20:41

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

Sun Apr 18 18:38:22 UTC 2021 up 10 days, 13:19, 1 user, load averages: 3.02, 3.27, 3.15

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.