Search for prime Gaussian-Mersenne norms (and G-M-cofactors) - Page 8

Cruelty · 2014-02-28, 15:08

Code:

till 600k - completed by Jean Penné (GQ-only effort)
600k - 700k - completed by Cruelty (GQ-only effort)
700k - GM36 - reserved by Thomas11 (GQ-only effort, factoring till 45 bits)
GM36 - 1.95M - completed by Cruelty (2 GMs + 5 GQs found)
1.95M - 2M - reserved by Cruelty (currently @ 1.98M)
2M - 3.5M - completed by Batalov (1 GQ found)
3.5M - 3.85M - reserved by Citrix (prefactored to 55 bits)
3.85M - 4M - reserved by Batalov

GM37-40M - pre-factored till 48 bits by Cruelty

@Thomas11 - sorry I haven't responded to your question earlier, and you've learned the "hard way" about testing/factoring for GQ-only effort

To the best of my knowledge there is no other file for the 700k-GM36 range. At the beginning of this effort I have pre-factored entire GM37-40M range till 48 bits so again, should anyone need it I can provide it

Thomas11 · 2014-02-28, 18:23

I completed factoring the range 700k-GM36 to 48 bits.
The number of candidates has significantly reduced from 19197 to 9544 (10152 at 45 bits).

I will continue factoring to 50 bits and perhaps a few bits higher until the elimination rate drops below the time for a primality test. Based on the timings at 700k and 992k I'm estimating that the whole range could be completed in about one month on a Core2Quad machine. That's much faster than I originally expected.

Citrix · 2014-03-01, 03:09

Quote:

Originally Posted by Thomas11

I completed factoring the range 700k-GM36 to 48 bits.
The number of candidates has significantly reduced from 19197 to 9544 (10152 at 45 bits).

I will continue factoring to 50 bits and perhaps a few bits higher until the elimination rate drops below the time for a primality test. Based on the timings at 700k and 992k I'm estimating that the whole range could be completed in about one month on a Core2Quad machine. That's much faster than I originally expected.

Thomas11, in your range, if LLR was used to test GM numbers then all numbers for which GM was tested, GQ would have automatically been tested. This should help eliminate some more tests.

I have had some luck with using p-1 for these numbers to sieve as 50-55 bits seems too low to sieve. P-1 is most useful when either a factor for GQ is know or GM is know and finding a new factor will eliminate the whole test. Also p-1 can be done on 64 bit computers, making the sieve more efficient. I am still working on how to process the output from prime95. Any suggestions?

Cruelty · 2014-03-01, 11:50

Quote:

Originally Posted by Citrix

I have had some luck with using p-1 for these numbers to sieve as 50-55 bits seems too low to sieve. P-1 is most useful when either a factor for GQ is know or GM is know and finding a new factor will eliminate the whole test. Also p-1 can be done on 64 bit computers, making the sieve more efficient. I am still working on how to process the output from prime95. Any suggestions?

Wouldn't it be more beneficial to pre-factor e.g. to 60 bits rather than P-1?

Citrix · 2014-03-01, 13:26

Quote:

Originally Posted by Cruelty

Wouldn't it be more beneficial to pre-factor e.g. to 60 bits rather than P-1?

Yes if I had enough 32 bit machines. I only have one machine. P-1 will still be useful after factoring to 60 bits.

Batalov · 2014-03-01, 15:49

32-bit binary gladly runs on any computer. This is true for the llr and e.g. for NewPGen (which only exists as a 32-bit binary) - these are both linked statically.

Thomas11 · 2014-03-01, 16:52

There may be a problem with LLR when looking at both sides (GM and GQ) and factoring is done in stages, e.g. first to 48 bits, then to 50 bits, and so on.

Consider for example n=702433, and let's assume we are testing both sides, using the switches TestGM=1 and TestGQ=1.

There would be two factors, one for each side:
2^702433-2^351217+1 has a factor : 376119154717
(2^702433+2^351217+1)/5 has a factor : 348149222345417

If factoring is done in just one step up to 50 bits, then both factors would be found and this n would be eliminiated.

If, however, one decides to factor to 48 bits first and in a later step to 50 bits, then this n would survive, since in the 48->50 bit stage LLR has no record about the smaller factor (376119154717) found in the earlier stage. Only if both factors would be found during one and the same factoring run, the number would be eliminated.

In practice this would mean that there might be quite a few candidates accidentally surviving the factoring stages. Perhaps one could write some shell or Perl script for extracting the factors from the lresults.txt files and check for matching pairs...

Citrix · 2014-03-01, 16:58

When checking in GM=1 and GQ=1 mode LLR does not write the factors unless factors for both GM=1 and GQ=1 have been found. Writing a script will not help because LLR does not output the factors.

Thomas11 · 2014-03-01, 17:18

Quote:

Originally Posted by Citrix

When checking in GM=1 and GQ=1 mode LLR does not write the factors unless factors for both GM=1 and GQ=1 have been found. Writing a script will not help because LLR does not output the factors.

Well, then running a "prefactoring stage" (as Cruelty did with FacTo=48) seperatelly of the primality testing could be counterproductive...

Citrix · 2014-03-01, 17:29

You have two options.. either sieve from scratch everytime
OR sieve GM and GQ separately (which will take twice the time) and then combine using the script.

Since I have sieved to 55 bits on my range there is no way I can move ahead to 60 bits (without repeating the work), that is why I am looking into p-1.

Cruelty · 2014-03-01, 22:30

Good point Thomas11 I haven't thought about it. From what I see, the original 32-bit pre-factored file found on jpenne.free.fr, does include information about GM-only or GQ-only factors, so perhaps there is an undocumented way to secure such information in factoring-only assignment?
As for my 48-bit effort it isn't completely useless, as there are less candidates to test, and at current range of "n" it doesn't take much time to again factor candidates till 48 bits and further.

2014-03-01, 16:52	#84
Thomas11 Feb 2003 2²×3²×53 Posts	There may be a problem with LLR when looking at both sides (GM and GQ) and factoring is done in stages, e.g. first to 48 bits, then to 50 bits, and so on. Consider for example n=702433, and let's assume we are testing both sides, using the switches TestGM=1 and TestGQ=1. There would be two factors, one for each side: 2^702433-2^351217+1 has a factor : 376119154717 (2^702433+2^351217+1)/5 has a factor : 348149222345417 If factoring is done in just one step up to 50 bits, then both factors would be found and this n would be eliminiated. If, however, one decides to factor to 48 bits first and in a later step to 50 bits, then this n would survive, since in the 48->50 bit stage LLR has no record about the smaller factor (376119154717) found in the earlier stage. Only if both factors would be found during one and the same factoring run, the number would be eliminated. In practice this would mean that there might be quite a few candidates accidentally surviving the factoring stages. Perhaps one could write some shell or Perl script for extracting the factors from the lresults.txt files and check for matching pairs... Last fiddled with by Thomas11 on 2014-03-01 at 16:58

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New PC dedicated to Mersenne Prime Search	Taiy	Hardware	12	2018-01-02 15:54
Gaussian integers- use of norms	devarajkandadai	Number Theory Discussion Group	11	2017-10-28 20:58
Low clock speeds on Mersenne Prime search	Ammonia	Hardware	2	2016-01-21 17:46
Testing Mersenne cofactors for primality?	CRGreathouse	Computer Science & Computational Number Theory	18	2013-06-08 19:12
Can I specify the range to search the Mersenne Prime?	Unregistered	Information & Answers	22	2012-03-20 11:38

2014-02-28, 18:23	#79
Thomas11 Feb 2003 774₁₆ Posts	I completed factoring the range 700k-GM36 to 48 bits. The number of candidates has significantly reduced from 19197 to 9544 (10152 at 45 bits). I will continue factoring to 50 bits and perhaps a few bits higher until the elimination rate drops below the time for a primality test. Based on the timings at 700k and 992k I'm estimating that the whole range could be completed in about one month on a Core2Quad machine. That's much faster than I originally expected.

2014-03-01, 15:49	#83
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²·23·103 Posts	32-bit binary gladly runs on any computer. This is true for the llr and e.g. for NewPGen (which only exists as a 32-bit binary) - these are both linked statically.

2014-03-01, 16:58	#85
Citrix Jun 2003 11000101110₂ Posts	When checking in GM=1 and GQ=1 mode LLR does not write the factors unless factors for both GM=1 and GQ=1 have been found. Writing a script will not help because LLR does not output the factors.

2014-03-01, 17:29	#87
Citrix Jun 2003 1582₁₀ Posts	You have two options.. either sieve from scratch everytime OR sieve GM and GQ separately (which will take twice the time) and then combine using the script. Since I have sieved to 55 bits on my range there is no way I can move ahead to 60 bits (without repeating the work), that is why I am looking into p-1.

2014-03-01, 22:30	#88
Cruelty May 2005 2³·7·29 Posts	Good point Thomas11 I haven't thought about it. From what I see, the original 32-bit pre-factored file found on jpenne.free.fr, does include information about GM-only or GQ-only factors, so perhaps there is an undocumented way to secure such information in factoring-only assignment? As for my 48-bit effort it isn't completely useless, as there are less candidates to test, and at current range of "n" it doesn't take much time to again factor candidates till 48 bits and further.