mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Proth Prime Search

Reply
 
Thread Tools
Old 2014-04-04, 15:38   #111
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·33·132 Posts
Default

Now you can do that! ;-)
Batalov is offline   Reply With Quote
Old 2014-04-04, 17:53   #112
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×33×132 Posts
Default

Warning: LLR prefactoring misses some factors.

This is in addition to the known bug that it hangs on some factors that are slightly smaller than 2^32 (has to be killed and restarted; reports a factor "1" and not necessarily for the correct side, i.e. GM/GQ). Examine your logs; each exponent with the reported factor of "1" should be rechecked with PARI ...or re-entered into the pool of candidates (or else one can miss a prime/PRP).

Examples:
Code:
1st kind:
2^4748941+2^2374471+1 has a factor : 1401773408617 [TF:1:62:mfaktc 0.20 75bit_mul32]
2^4770839-2^2385420+1 has a factor : 15737871942997 [TF:1:62:mfaktc 0.20 75bit_mul32]
2^4772107+2^2386054+1 has a factor : 22894106978789 [TF:1:62:mfaktc 0.20 75bit_mul32]
2^4739143-2^2369572+1 has a factor : 115378303475689 [TF:1:62:mfaktc 0.20 75bit_mul32]
2^4769593-2^2384797+1 has a factor : 209112235666913 [TF:1:62:mfaktc 0.20 75bit_mul32]

2nd kind (these are found with PARI/gp):
4766423 4289780701      +       /5
4777781 4280891777      -       /5
4824697 4284330937      -
4898687 4291249813      -
4944817 4292101157      +       /5
4957219 4283037217      -       /5
4961477 4286716129      +
4989353 4290843581      -
5020591 4277543533      +       /5
Batalov is offline   Reply With Quote
Old 2014-04-04, 23:09   #113
Citrix
 
Citrix's Avatar
 
Jun 2003

112×13 Posts
Default

Quote:
Originally Posted by Batalov View Post
Warning: LLR prefactoring misses some factors.
I looked through my logs. I have not had any case where LLR reports a factor "1". Is this limited to factors <2^32 or on a particular machine/chipset?

If it is limited to <2^32, is it safe to use the file on Jean's website?
Citrix is offline   Reply With Quote
Old 2014-04-05, 00:33   #114
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·33·132 Posts
Default

2nd kind is limited to 2^32 in size. It is probably also confounded to some 32-bit emulation problem on 64-bit computers (checked on both Win7 64 and linux64); but I cannot check 32-bit comps - it's been a while since I've seen one. If you have one, can you check type 1* and type 2 errors as shown above on it?

I've never looked at Jean's file but it looks ok (now that I've looked at it); he must have used a 32-bit OS.

______________
*actually, this is easily checked from your LLR_GM file: all five examples of type 1 are retained in it, so the factors were not found.
Attached Thumbnails
Click image for larger version

Name:	Type2example.png
Views:	74
Size:	9.4 KB
ID:	10998  

Last fiddled with by Batalov on 2014-04-05 at 00:38
Batalov is offline   Reply With Quote
Old 2014-04-05, 17:09   #115
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216468 Posts
Default

{(2^{2396029} -1)^2+1}\over 2 is prime (1442553 digits)
Batalov is offline   Reply With Quote
Old 2014-04-05, 17:47   #116
Citrix
 
Citrix's Avatar
 
Jun 2003

112·13 Posts
Default

Congratulations!

I don't completely understand your previous post (with the software bug). Do we need to re-do any ranges for a missed prime etc or are we good?
Citrix is offline   Reply With Quote
Old 2014-04-05, 18:24   #117
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·33·132 Posts
Default

The missed factors (1st kind) are not dangerous per se, because they produce false negatives only (a factor is missed), so the candidate lives on, goes through a more computationally expensive N-1 test. It is still checked, which is good. We wouldn't even know that a factor exists without gmqfaktc (because these factors are not tiny, too large for PARI).

For the 2nd kind: well, I cannot check a 32-bit behavior, but I conjecture (based on Jean's output files) that LLR 32-bit sieve works properly on 32-bit CPUs, but has rare but reproducible hiccups on the 64-bit CPUs. If you ran 32-bit LLR only in 32-bit setting, you should be fine (and you report that there were no hangups like shown above). However, if you (or LLR in its output files) removes a candidate from N-1 testing then there will exist some unchecked candidates that don't really have a factor. When one runs the LLR32 on a 64-bit OS, everything mostly runs fine, and then every once in a while LLR says "has factor : 1" and does not output such candidate to the output stream.

I run the PARI validation on all factors before removing the candidates. Like this (./validator.pl < factors | gp -q):
Code:
#!/usr/bin/perl -w

while(<>) {
    s/\s+$//;
    if(/^\(?2\^(\d+)([+-])2\^(\d+).*has a factor *: (\d+)/) {
        print "f=Mod(2,$4);if(f^",$1,$2,"f^",$3,"+1,print(\"NOT $_\"))\n" if $4 > 2;
    } elsif(/^\(?2\^(\d+)([+-]).*has a factor *: (\d+)/) {
        print "f=Mod(2,$3);if(f^",$1,$2,"f^",($1+1)/2,"+1,print(\"NOT $_\"))\n" if $3 > 2;
    }
}
The validator prepares a fast modular check one-liner and feeds it to PARI/gp.
Batalov is offline   Reply With Quote
Old 2014-04-05, 18:50   #118
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216468 Posts
Default The debug cases

Here is the short test.
Prerequisites:
1. A 32-bit LLR binary (you can try various versions)
2. Use this llr.ini
Code:
FacTo=48
TestGM=1
TestGQ=0
PgenInputFile=test1.txt
PgenOutputFile=out1.txt
3. Use this test1.txt
Code:
ABC4^$a+1
4748941
4770839
4772107
4739143
4769593

4766423
4777781
4824697
4898687
4944817
Results: the first five candidates will not produce a factor (but they have them, and less than 48 bits); on the sixth (and below), the program first pause (on screen will report incorrect factor found, will sleep for five minutes and the will repeat that until stopped manually), then if/when stopped manually, will report a factor of 1 and will not put the candidate into "out1.txt". The linux CL program will do the same; it will accept a kill signal and will report a factor of 1, will proceed to next line, and will not put the candidate into "out1.txt" (i.e. the same).
Batalov is offline   Reply With Quote
Old 2014-04-05, 19:15   #119
Citrix
 
Citrix's Avatar
 
Jun 2003

112·13 Posts
Default

On a 64 bit machine running a 32 bit LLR I get the same errors.
On a 32 bit machine running a 32 bit LLR, LLR finds the factors for lines 1-5 but gets stuck on lines 6-10.

Should we re-sieve the whole untested range? What % of factors is LLR missing?

Does this bug depend on the size of the exponent of the GM/GQ number? None of my sieve files have this error? May be it only occurs in 4.7M+ range?

Last fiddled with by Citrix on 2014-04-05 at 19:17
Citrix is offline   Reply With Quote
Old 2014-04-05, 20:21   #120
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A616 Posts
Default

I have seen this bug since the beginning - it is everywhere (not just for p>4.7M; this was just my recent range), but it is understandably patchy (see below). I think there is an overflow and it happens when (1-ε)*2^32 < f < 2^32. ε is small.

Now, why is it patchy? Because f = 4kp + 1, and for some ranges of p, there are no f values that enter the dangerous interval (and when some f does, it still needs to be prime, and if it is not, it is silently dismissed without a bug).

I've already run an emulation (it is easier done in PARI, because... well, because to find these in LLR, one needs to manually kill the processes multiple times - and it is tedious). So, I have identified all small p for which the bug occurs and rechecked all of them, first for legitimate factors and then with N-1. I have done this for my intervals. But I didn't do it recently for other ranges. Last time I ran it was for all p<3M, iirc. This can be repeated, to be safe; this is a nice little DC project for someone: little because there are really very few of these.
Batalov is offline   Reply With Quote
Old 2014-04-06, 00:50   #121
Citrix
 
Citrix's Avatar
 
Jun 2003

112·13 Posts
Default

Quote:
Originally Posted by Batalov View Post
I have seen this bug since the beginning - it is everywhere (not just for p>4.7M; this was just my recent range), but it is understandably patchy (see below). I think there is an overflow and it happens when (1-ε)*2^32 < f < 2^32. ε is small.

Now, why is it patchy? Because f = 4kp + 1, and for some ranges of p, there are no f values that enter the dangerous interval (and when some f does, it still needs to be prime, and if it is not, it is silently dismissed without a bug).

I've already run an emulation (it is easier done in PARI, because... well, because to find these in LLR, one needs to manually kill the processes multiple times - and it is tedious). So, I have identified all small p for which the bug occurs and rechecked all of them, first for legitimate factors and then with N-1. I have done this for my intervals. But I didn't do it recently for other ranges. Last time I ran it was for all p<3M, iirc. This can be repeated, to be safe; this is a nice little DC project for someone: little because there are really very few of these.

The Type II error can be avoided by using the format
N GMfactor GQfactor

eg) N 1 1


I got the following output on a 64 bit machine.
Code:
2^4898687-2^2449344+1 has a factor : 89391240377
2^4944817-2^2472409+1 has a factor : 46224149317
I used the above format for all my sieve work, so I think I am safe from missing a prime.

LLR is still missing factors (Type I error). I am not sure if I would want to continue doing the painfully long N-1 test, if a small factor exists. I would like to find the small factors first. Is there a 64 bit windows binary for gmqfaktc? What is the input format?
Citrix is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 12:55.

Sat Sep 26 12:55:45 UTC 2020 up 16 days, 10:06, 1 user, load averages: 1.87, 2.27, 2.04

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