Unexpected ECM factor from Prime95

philmoore · 2007-05-09, 23:10

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 21-digit 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 Lucas-Lehmer 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.

akruppa · 2007-05-09, 23:53

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,94201-smooth) is sigma=2382564360

Alex

akruppa · 2007-05-09, 23:58

Which version of Prime95 found the factor?

Alex

Prime95 · 2007-05-10, 00:39

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.

philmoore · 2007-05-10, 03:07

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.

akruppa · 2007-05-10, 08:39

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.

Alex

akruppa · 2007-05-10, 09:00

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.

Alex

Andi47 · 2007-05-10, 09:47

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?

akruppa · 2007-05-10, 09:55

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 round-off error, and iirc the ECM code in Prime95 cuts some corners when adding/multiplying by constant the FFT-ready 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 re-run 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

Prime95 · 2007-05-10, 13:47

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.

philmoore · 2007-05-10, 16:45

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.

2007-05-10, 00:39	#4
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 19×397 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 2007-05-10 at 00:42

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Does Prime95 stop when factor is found?	jovada	Information & Answers	13	2016-08-13 15:05
Unexpected Factor	apocalypse	PrimeNet	6	2015-03-15 19:31
unexpected excrement	fivemack	Msieve	5	2011-05-09 23:38
Make Prime95 continue after finding a factor?	wblipp	Software	1	2003-09-20 07:25
Record ECM factor found by Prime95	philmoore	Lounge	0	2003-06-24 20:41

2007-05-09, 23:10	#1
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 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 21-digit 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 Lucas-Lehmer 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.

2007-05-09, 23:53	#2
akruppa "Nancy" Aug 2002 Alexandria 2467₁₀ 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,94201-smooth) is sigma=2382564360 Alex

2007-05-09, 23:58	#3
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Which version of Prime95 found the factor? Alex

2007-05-10, 03:07	#5
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 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.

2007-05-10, 09:47	#8
Andi47 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?

2007-05-10, 09:55	#9
akruppa "Nancy" Aug 2002 Alexandria 2467₁₀ 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 round-off error, and iirc the ECM code in Prime95 cuts some corners when adding/multiplying by constant the FFT-ready 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 re-run 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

2007-05-10, 13:47	#10
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 19×397 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.

2007-05-10, 16:45	#11
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 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.