mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-05-09, 23:10   #1
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

112010 Posts
Default 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.
philmoore is offline   Reply With Quote
Old 2007-05-09, 23:53   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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 is offline   Reply With Quote
Old 2007-05-09, 23:58   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Which version of Prime95 found the factor?

Alex
akruppa is offline   Reply With Quote
Old 2007-05-10, 00:39   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11111100101002 Posts
Default

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
Prime95 is offline   Reply With Quote
Old 2007-05-10, 03:07   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

25·5·7 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2007-05-10, 08:39   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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

Last fiddled with by akruppa on 2007-05-10 at 08:49 Reason: Added mprime 23.9 test case
akruppa is offline   Reply With Quote
Old 2007-05-10, 09:00   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-05-10, 09:47   #8
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

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?
Andi47 is offline   Reply With Quote
Old 2007-05-10, 09:55   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-05-10, 13:47   #10
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11111100101002 Posts
Default

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.
Prime95 is offline   Reply With Quote
Old 2007-05-10, 16:45   #11
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

46016 Posts
Default

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.
philmoore is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 14:49.


Thu Dec 1 14:49:28 UTC 2022 up 105 days, 12:18, 1 user, load averages: 1.34, 1.05, 1.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔