mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2012-10-04, 03:42   #78
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Code:
1257787: k = 8,29,48,53,84,92,93,113,149,168,212,228,249,308,348,420,425,504,540,569,572,573,600,665,684,729,785,809,812,849,872,888,893
1398269: k = 5,44,68,93,140,180,236,240,248,273,293,296,356,453,521,545,549,560,608,609,644,684,713,720,728,753,824,849,861,909,968
2976221: k = 56,80,84,96,144,153,164,245,248,264,296,381,441,461,465,501,509,528,536,668,681,749,756,780,788,909,956,996
3021377: k = 44,60,81,104,105,116,189,245,249,264,333,341,345,420,440,480,548,564,608,609,641,653,660,669,768,888,905,941,944,980
6972593: k = 5,24,68,89,96,101,153,168,185,285,329,336,369,408,453,465,468,473,485,521,593,629,648,720,741,749,809,840,860,884,929,948,956
13466917: k = 8,69,89,93,96,125,128,168,204,209,221,225,233,264,324,348,368,380,413,440,453,473,476,524,540,576,629,644,653,660,728,804,821,876,896,909,944,953,960,984
20996011: k = 8,113,224,249,272,300,333,348,425,429,477,485,564,569,608,645,657,680,740,837,849,893,900
24036583: k = 8,12,48,65,68,113,125,152,209,212,285,305,308,393,404,473,485,488,497,533,573,593,617,669,672,708,728,768,824,833
25964951: k = 45,68,164,168,177,180,257,305,332,369,389,429,432,444,473,488,537,552,593,597,608,648,657,660,672,713,752,780,812,828,893,917,944,980
30402457: k = 41,89,96,113,116,156,173,176,216,261,264,273,288,309,320,389,456,468,476,525,533,573,581,608,629,641,644,701,716,720,744,765,809,816,896,965,993
32582657: k = 20,44,60,108,140,216,221,273,276,305,324,353,356,413,429,453,489,513,528,576,600,608,716,720,761,809,849,860,884,921,944,980
37156667: k = 24,44,48,77,80,104,168,173,212,233,308,324,332,368,405,429,437,468,480,524,525,537,552,557,569,600,605,684,693,713,753,777,828,864,917,944
42643801: k = 33,44,69,96,189,221,233,285,293,345,369,380,393,428,441,468,485,504,509,624,648,716,740,744,749,768,813,816,833,873,876,924,996
43112609: k = 5*,185,200*,201,216*,233,273,384*,401*,429*,513,521,560,593,600*,656,660,665*,668,669*,684,713,753,800,809,860,888,933*,944,965

* = Since proven composite via deeper sieving to 1e11.
If I recall correctly, the results I posted on Will's web-page involved sieving each exponent from 2976221 to 30402457 up to 2^31. I probably have the factors I found somewhere around here, Ernst, although because of a hard-drive failure a few years ago, it may be in the form of a "printout", an antiquated form of storage frequently used in the 20th century.
philmoore is offline   Reply With Quote
Old 2012-10-04, 05:53   #79
axn
 
axn's Avatar
 
Jun 2003

24·5·67 Posts
Default

Quote:
Originally Posted by philmoore View Post
the results I posted on Will's web-page involved sieving each exponent from 2976221 to 30402457 up to 2^31.
Is that k <= 2^31 (in which case, how deep was it sieved) or sieved up to 2^31 (in which case, what was the k range)?
axn is online now   Reply With Quote
Old 2012-10-04, 05:55   #80
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110111010102 Posts
Default

Sorry for the delay, no free time, I just found a bit of time during lunch break but I could not access the computer (remoting to my house, I think out IT dept did something with the firewall or the servers during the lunch).

Now I got it. The k's which were eliminated in my table were:
Code:
#34:  1257787: k = 149,249,504,600,785,872
#35:  1398269: k = 180,240,248,273,609,849
#36:  2976221: k = 56,528,996
#37:  3021377: k = 81,333,420,608,660
#38:  6972593: k = 68,185,336,369,453,741,884,956
#39: 13466917: k = 69,93,96,476,576,653,953
#40: 20996011: k = 113,272,657,740
#41: 24036583: k = 113
#42: 25964951: k = 164,473,657,713,893,944
#43: 30402457: k = 176,261,273,288,641,744
#44: 32582657: k = 44,221,273,453,489,576,720,944,980
#45: 37156667: k = 524,693,713,944
#46: 42643801: k = 44,221,393,428,744
#47: 43112609: k = none
This list is "have factors between 32M and 1G", they have to be asterisked in - or eliminated from - ewmayer's table. Their factors (except for #46,k=44, whose factor is between 1G and 4G) are:

Code:
#34,149 has a factor : 306852607
#34,249 has a factor : 41338111
#34,504 has a factor : 91596737
#34,600 has a factor : 135549677
#34,785 has a factor : 57979847
#34,872 has a factor : 370969009

#35,180 has a factor : 452535697
#35,240 has a factor : 150051247
#35,248 has a factor : 60082859
#35,273 has a factor : 234717979
#35,609 has a factor : 585942169
#35,849 has a factor : 352875203

#36, 56 has a factor : 147547391
#36,528 has a factor : 41221249
#36,996 has a factor : 646207649

#37, 81 has a factor : 76165591
#37,333 has a factor : 427066817
#37,420 has a factor : 411433669
#37,608 has a factor : 33456589
#37,660 has a factor : 809870977

#38, 68 has a factor : 34411649
#38,185 has a factor : 386501543
#38,336 has a factor : 439589651
#38,369 has a factor : 738469559
#38,453 has a factor : 36832979
#38,741 has a factor : 896870687
#38,884 has a factor : 45868327
#38,956 has a factor : 58198181

#39, 69 has a factor : 119370001
#39, 93 has a factor : 33674209
#39, 96 has a factor : 194242183
#39,476 has a factor : 203942419
#39,576 has a factor : 307063187
#39,653 has a factor : 333708901
#39,953 has a factor : 565776451

#40,113 has a factor : 33208589
#40,272 has a factor : 227322647
#40,657 has a factor : 33082001
#40,740 has a factor : 108790961

#41,113 has a factor : 492502253

#42,164 has a factor : 168153533
#42,473 has a factor : 47613217
#42,657 has a factor : 67042249
#42,713 has a factor : 88283473
#42,893 has a factor : 601958087
#42,944 has a factor : 60004817

#43,176 has a factor : 72848761
#43,261 has a factor : 127585477
#43,273 has a factor : 297084287
#43,288 has a factor : 193964599
#43,641 has a factor : 542210323
#43,744 has a factor : 479934337

#44, 44 has a factor : 415021787
#44,221 has a factor : 77249351
#44,273 has a factor : 994172791
#44,453 has a factor : 120304357
#44,489 has a factor : 138744079
#44,576 has a factor : 33481247
#44,720 has a factor : 231810473
#44,944 has a factor : 101857159
#44,980 has a factor : 220184941

#45,524 has a factor : 53040683
#45,693 has a factor : 232066663
#45,713 has a factor : 177675227
#45,944 has a factor : 101350111

#46, 44,   tested to : 1000000007, no factor.
#46,221 has a factor : 161362987
#46,428 has a factor : 514204841
#46,744 has a factor : 85648273
#46,393 has a factor : 421524893
LaurV is offline   Reply With Quote
Old 2012-10-04, 07:14   #81
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·7·173 Posts
Default

Nice job, folks, thank you very much!

The DB for this search is ready, I will work out some online tables during the weekend (or even earlier, if I find time), so that everyone will have a clear idea of who is doing what at which level...

@Ernst, thank you for the ks; your software is great as is, no need to continue sieving after a factor is found.

@Phil, thank you for the information about your sieving work.

@LaurV, M#42 and M#46 have been checked up to 10G, five k have been cleared, I collected the factors for double-checks. M#47 is being taken to 1T. I am attaching your table with my extensions here, please confirm or correct your claimed ranges .

I will work on automatic reservation system as I get started with the tables management.

BTW, any ideas for a name of this sieving project?

Luigi
Attached Files
File Type: zip mmpp.zip (6.6 KB, 146 views)

Last fiddled with by ET_ on 2012-10-04 at 07:16
ET_ is offline   Reply With Quote
Old 2012-10-04, 09:55   #82
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

23616 Posts
Smile Some basic questions

I am following this discussion with great interest. Sorry for draging it down to a basic level and at the same time exploring my ignorance , so if I may I would like to ask a few basic questions, just making sure that I have understood what it is all about,

1. So what you are doing right now is to sieve to find possible candidates that might divide the very large double mersennes MM#34 - MM#47. What you find is possible candidates that might divide MM#34 - MM#47 respectively. Is that rignt?

2. So when you are speaking of "factors" you are not speaking of factors of the double mersennes but factors of the possible candidates which have the form 2*k*[M#34-M#47]+1 for different k:s. Is that right? So it is rather factors of possible factors and these factors of factors do not have any special form known?

3. And the reason why you are not using the candidates found for TF of MM#34-MM#47 is that these numbers are so increadibly large that, presently there is no program available that could do such a TF. Is that right?

4. And if you find a factor of MM#47 that factor would be larger then M#47 hence the largest prime found? Is that right?

Once again sorry for asking these basic questions!
aketilander is offline   Reply With Quote
Old 2012-10-04, 10:08   #83
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

26EA16 Posts
Default

Quote:
Originally Posted by aketilander View Post
3. And the reason why you are not using the candidates found for TF of MM#34-MM#47 is that these numbers are so increadibly large that, presently there is no program available that could do such a TF. Is that right?
You got it all right, except number 3. Doing a TF for a double mersenne, you have to compute 2^{2^p-1}-1 mod q=2*k*(2^p-1)+1, which is equivalent to raise 2^(2^p) and check if this is 2 (mod q). This means you have to, in fact, take x=2, and square it p times, mod q. Many programs can do that, including P95, but the time involved would be the same amount of time as LL-ing Mp (is exactly the same type and amount of computation like a LL test, the modulus q has just few bits more then Mp, when we do mod Mp on a "clasic" LL test).

i.e. to LL any Mp (the job we normally do for GIMPS), you start with s0=4 and do sn+1=sn2-2 (mod Mp), p-2 times

otoh, to test if 2*k*Mp+1 divides MMp, you start with s0=2 and do sn+1=sn2 (mod 2*k*Mp+1), exactly p times (so there are two more iterations), and the mod is just few bits (for a small k) bigger then Mp (taking about the same time, in fact).

The time will be the same like doing LL test for exponent p (about).

Last fiddled with by LaurV on 2012-10-04 at 10:18
LaurV is offline   Reply With Quote
Old 2012-10-04, 10:31   #84
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2×17×293 Posts
Default

A small observation about question 4 (deliberately a separate post, do be easy visible, and not lost in the TL;DR text of the former post):

If we find a factor q=2*k*M#47+1 of MM#47, for such a small k [in fact for ANY k smaller than or equal to (M#47+2)], that number q will be higher then 2*M#47+1 (in fact, larger than, or equal to 2*185*M#47+1).

And that factor q will be PRIME.

And it will be for the first time in a VERY LONG history when the LARGEST KNOWN PRIME is not a mersenne number.

Last fiddled with by LaurV on 2012-10-04 at 10:47
LaurV is offline   Reply With Quote
Old 2012-10-04, 10:59   #85
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

56610 Posts
Smile

Quote:
Originally Posted by LaurV View Post
And that factor q will be PRIME.

And it will be for the first time in a VERY LONG history when the LARGEST KNOWN PRIME is not a mersenne number.
That would indeed be sensational!!!
aketilander is offline   Reply With Quote
Old 2012-10-04, 13:32   #86
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·7·173 Posts
Default

Quote:
Originally Posted by philmoore View Post
If I recall correctly, the results I posted on Will's web-page involved sieving each exponent from 2976221 to 30402457 up to 2^31. I probably have the factors I found somewhere around here, Ernst, although because of a hard-drive failure a few years ago, it may be in the form of a "printout", an antiquated form of storage frequently used in the 20th century.
How many k did you sieve up to 2^31, per exponent?

Luigi
ET_ is offline   Reply With Quote
Old 2012-10-04, 18:45   #87
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

32×1,303 Posts
Default

Quote:
Originally Posted by LaurV View Post
You got it all right, except number 3. Doing a TF for a double mersenne, you have to compute 2^{2^p-1}-1 mod q=2*k*(2^p-1)+1, which is equivalent to raise 2^(2^p) and check if this is 2 (mod q). This means you have to, in fact, take x=2, and square it p times, mod q. Many programs can do that, including P95, but the time involved would be the same amount of time as LL-ing Mp (is exactly the same type and amount of computation like a LL test, the modulus q has just few bits more then Mp, when we do mod Mp on a "clasic" LL test).

i.e. to LL any Mp (the job we normally do for GIMPS), you start with s0=4 and do sn+1=sn2-2 (mod Mp), p-2 times

otoh, to test if 2*k*Mp+1 divides MMp, you start with s0=2 and do sn+1=sn2 (mod 2*k*Mp+1), exactly p times (so there are two more iterations), and the mod is just few bits (for a small k) bigger then Mp (taking about the same time, in fact).

The time will be the same like doing LL test for exponent p (about).
You got the gist of it right, but the work estimate is an order of magnitude too optimistic, because there is no fast DWT-method for multiply modulo such candidate factors, as there is for the multiply modulo Mp used in LL testing, and p-1/ecm done on Mp. As a result one must do a generalized modmul. In my code - which does not yet have the FFT-enabled versions of all these needed to do this efficiently on the really big M(Mp) - I use a Montgomery-mul-based modpow algorithm, which needs not 1 bignum MUL (as for LL) but 3 MUL operations, as detailed on p.3 of the draft manuscript I posted in this Math forum thread. The only part of that MUL sequence which permits optimization beyond general FFT-based MUL is the final UMULH_b(q, lo), which can take advantage of the special form of q for double-Mersennes to achieve the result with just some shift/add/scalar-mul work. So the best one could hope to achieve is a per-powering-bit time perhaps 3-5x longer than the per-iteration time for LL run on the same Mp.

Also note - and I don't mean to damp folks' enthusiasm here, just to set realistic expectations - that for the kinds of M(Mp) we're discussing here, the fact that a given candidate q has no factors below (say) 10^15 or even ~10^20 (probabilistically, if one follows the TF with p-1 and/or ecm) only slightly increases the odds of q being prime, from [a very small number] to perhaps 2 or 3 times [a very small number]. Of course such a find would be spectacular, and one does not improve the methods available for attempting such a feat by giving up because the odds seem to be so daunting. One can learn much from failed attempts, if one approaches such projects from an algorithmic-improvement perspective, rather than one of "my life will only have meaning if this succeeds".

---------------------------

p.s. to Luigi: My run of MM#47(k=185) is to 10T, not 1T. (97% complete as I write this, odds of finding a factor in the final 3% very small). If folks want to do this one very deeply, I suggest divvying up the range 10-100T into 9 10T-sized chunks and handing those out to people interested in asssigning 1 or more CPU to the task.
ewmayer is offline   Reply With Quote
Old 2012-10-04, 19:11   #88
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22×7×173 Posts
Default

Quote:
Originally Posted by ewmayer View Post
---------------------------

p.s. to Luigi: My run of MM#47(k=185) is to 10T, not 1T. (97% complete as I write this, odds of finding a factor in the final 3% very small). If folks want to do this one very deeply, I suggest divvying up the range 10-100T into 9 10T-sized chunks and handing those out to people interested in asssigning 1 or more CPU to the task.
Yes, I have 10T on my scrapboard, thank you.

The idea was indeed to take the first 1000 k that survive low-level sieving to (say) 1T, and then dedicate resources to deep-sieving the first candidate of each row (exponent), in the hope of enhancing our knowledge about the limits of these ranges.

The idea of using 9 ranges of 10T to get to 100T is nice, but risky: if you dedicate your hardware to test 40T-100T, you would not be happy when I will tell you that the factor was hidden on the 10T-20T range.
A different approach could be testing the first candidate of each exponent in parallel to minimize the risk, but then we may not find a record non-Mersenne prime.

Anyway, I don't think there will be much audience for this project, and my worries may as well disappear. Said from the one who launched the Operation Billion Digits with William Lipp.

On another thought, without OBD we would not have had mfaktc...

Luigi

Last fiddled with by ET_ on 2012-10-04 at 19:11
ET_ is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really. CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55
Official "World cup 2014/2018" teat LaurV Hobbies 74 2018-07-11 19:33
Problem E7 of Richard Guy's "Unsolved problems in number theory" Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19
Is the USA the "new" peacekeeper of the world?? outlnder Soap Box 20 2005-02-03 09:30
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 08:30.


Sun May 22 08:30:13 UTC 2022 up 38 days, 6:31, 0 users, load averages: 1.68, 1.31, 1.12

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.

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