20070509, 23:10  #1 
"Phil"
Sep 2002
Tracktown, U.S.A.
1120_{10} Posts 
Unexpected ECM factor from Prime95
I had an unexpected factor turn up running ECM on M65537:
[Tue May 08 20:37:48 2007] ECM found a factor in curve #1, stage #2 Sigma=5680450114125612, B1=1000000, B2=100000000. M65537 has a factor: 513668017883326358119 Unexpected, because the factor is only 21 digits. The status page says this number has had a complete number of curves run at the 25 and 30 digit levels, 400 curves at the 35 digit level, and 100 curves at the 40 digit level. (I myself ran 400 curves at the 30 digit level and the listed curves at the 35 and 40 digit levels, most run before 2002.) One would have expected a 21digit factor to have turned up long ago, but here it is. Which leads to a question: was there some sort of bug in an older version of Prime95 that caused this factor to be missed? This particular Mersenne number has some historical significance, as Mersenne himself apparently believed it was prime, as the Fermat prime exponent is one more than a power of 2. However, Mersenne was wrong about 257 being a Mersenne prime exponent, and he was wrong about this one as well. I am not positive, but I think that the first LucasLehmer test on it may have been run by Landon Curt Noll. (I have asked him, but haven't yet received confirmation.) I'll run a few more curves and see if any more factors turn up. 
20070509, 23:53  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
This factor comes as a surprise, to say the least.
According to my Pari/GP program, the probability of missing this factor with 400 curves at B1=1M, B2=100M is about 10^{19}, so I don't think it could have been a case of merely having had bad luck so far. A sigma value for which B1=11000, B2=1100000 finds the factor (in fact, the order is 6547,94201smooth) is sigma=2382564360 Alex 
20070509, 23:58  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Which version of Prime95 found the factor?
Alex 
20070510, 00:39  #4 
P90 years forever!
Aug 2002
Yeehaw, FL
1111110010100_{2} Posts 
Human error? That factor is already known. However it is not included in the lowm.txt file. Perhaps you manually added it to lowm.txt back in 2002?
I'll add it to lowm.txt next time it is updated. I'll also correct ecm2.htm to indicate that the number has known factors. Last fiddled with by Prime95 on 20070510 at 00:42 
20070510, 03:07  #5 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}·5·7 Posts 
I don't know when the factor was discovered, but I did not know about it and never added it to lowm.txt, so I still suspect that the prime95 program was malfunctioning in not discovering it. There is an outside chance that all three of the machines I used in the factoring had hardware problems, but I doubt it, as these machines were also responsible for the discovery of several other genuinely new factors.
I will check tomorrow when I am back at my office, but I think that the version that found the factor was 24.12 or 24.13. 
20070510, 08:39  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Will Edgington's lowM.txt file does not list the factor, either, neither did a Google search for it yield a result. Since this is a rather prominent exponent, Fermat prime and being one of Mersenne's original guessed and all, I would have expected the factor to circulate a bit after discovery. George, do you remember who originally discovered it?
mprime 23.9 can find it: Code:
Mersenne number primality test program version 23.9 ECM on M65537: curve #1 with s=2382564360, B1=11000, B2=1100000 [May 10 10:47] At prime 709. Time thusfar 0.560 sec. [May 10 10:47] At prime 1511. Time thusfar 1.112 sec. [May 10 10:47] At prime 2311. Time thusfar 1.659 sec. [May 10 10:47] At prime 3119. Time thusfar 2.209 sec. [May 10 10:47] At prime 3907. Time thusfar 2.759 sec. [May 10 10:47] At prime 4691. Time thusfar 3.308 sec. [May 10 10:47] At prime 5501. Time thusfar 3.858 sec. [May 10 10:47] At prime 6271. Time thusfar 4.406 sec. [May 10 10:47] At prime 7039. Time thusfar 4.955 sec. [May 10 10:47] At prime 7867. Time thusfar 5.506 sec. [May 10 10:47] At prime 8677. Time thusfar 6.058 sec. [May 10 10:47] At prime 9421. Time thusfar 6.609 sec. [May 10 10:47] At prime 10181. Time thusfar 7.158 sec. Stage 1 complete. 281591 transforms, 1 modular inverses. Time: 7.701 sec. Stage 2 init complete. 10389 transforms, 1 modular inverses. Time: 0.368 sec. [May 10 10:47] At prime 90731. Time thusfar 0.631 sec. [May 10 10:47] At prime 236881. Time thusfar 1.178 sec. [May 10 10:47] At prime 390647. Time thusfar 1.731 sec. [May 10 10:47] At prime 546841. Time thusfar 2.279 sec. [May 10 10:47] At prime 708131. Time thusfar 2.835 sec. [May 10 10:47] At prime 869413. Time thusfar 3.382 sec. [May 10 10:47] At prime 1035733. Time thusfar 3.937 sec. Stage 2 complete. 157173 transforms, 2 modular inverses. Time: 4.450 sec. Stage 2 GCD complete. Time: 0.040 sec. M65537 has a factor: 513668017883326358119 There are no more exponents to test. Please send the results.txt file to woltman@alum.mit.edu Contact the PrimeNet server for more exponents. Last fiddled with by akruppa on 20070510 at 08:49 Reason: Added mprime 23.9 test case 
20070510, 09:00  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
mprime 22.12 does NOT find it:
Code:
Mersenne number primality test program version 22.12 ECM on M65537: curve #1 with s=2382564360, B1=11000, B2=1100000 Stage 1 complete. 281591 transforms, 1 modular inverses. Time: 7.839 sec. Stage 2 init complete. 3825 transforms, 1 modular inverses. Time: 0.184 sec. Stage 2 complete. 165955 transforms, 20 modular inverses. Time: 6.009 sec. Stage 2 GCD complete. Time: 0.051 sec. There are no more exponents to test. Please send the results.txt file to woltman@alum.mit.edu Contact the PrimeNet server for more exponents. 
20070510, 09:47  #8 
Oct 2004
Austria
2×17×73 Posts 
I guess now somebody should check wich curves on which exponents have been run with Mprime 22.12  maybe some exponents need redoing for t25 and t30 ranges?

20070510, 09:55  #9 
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
We should first try to find out what exponents are affected. It might be that exponents so close to a power of two use an FFT length that pushes the roundoff error, and iirc the ECM code in Prime95 cuts some corners when adding/multiplying by constant the FFTready data. Maybe this has lead to frequent rounding error for this exponent. However, this is only a wild guess  my point is that we should not rerun a lot of ECM until we know a little more about what the problem is. Also, if ECM at higher bounds with a later version of Prime95 has been done on a number, it would be useless to test it again with lower bounds. The higher bounds would have found small factors by now.
Alex 
20070510, 13:47  #10 
P90 years forever!
Aug 2002
Yeehaw, FL
1111110010100_{2} Posts 
I'm not too thrilled about spending a lot of time debugging a version 22 problem. The problem shouldn't be too widespread as many factors were found in the ecm1.htm and ecm2.htm tables using that version.
I cannot find the email that first reported the factor. According to the source code, both v22 and v24 should use the 3K FFT size. Exponents up to 65729 use that FFT size. 
20070510, 16:45  #11 
"Phil"
Sep 2002
Tracktown, U.S.A.
460_{16} Posts 
The version I am currently using is 24.14. Five or six years ago, I ran curves on this number on a 233 MHz Pentium and also on two 400 MHz Pentium 2 machines, but I don't know what version of Prime95 they were using. I wonder if Alex might be right, that exponents close to an FFT boundary were the ones affected.
What is your source, George, in saying that this factor was already known? I'm wondering if it was reported by someone using a different program, and that could be the reason you never updated your status page. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Does Prime95 stop when factor is found?  jovada  Information & Answers  13  20160813 15:05 
Unexpected Factor  apocalypse  PrimeNet  6  20150315 19:31 
unexpected excrement  fivemack  Msieve  5  20110509 23:38 
Make Prime95 continue after finding a factor?  wblipp  Software  1  20030920 07:25 
Record ECM factor found by Prime95  philmoore  Lounge  0  20030624 20:41 