mersenneforum.org Search for prime Gaussian-Mersenne norms (and G-M-cofactors)
 Register FAQ Search Today's Posts Mark Forums Read

 2014-04-04, 15:38 #111 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 27×71 Posts Now you can do that! ;-)
 2014-04-04, 17:53 #112 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 27·71 Posts 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
2014-04-04, 23:09   #113
Citrix

Jun 2003

2·33·29 Posts

Quote:
 Originally Posted by Batalov 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?

 2014-04-05, 00:33 #114 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 908810 Posts 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   Last fiddled with by Batalov on 2014-04-05 at 00:38
 2014-04-05, 17:09 #115 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 27·71 Posts ${(2^{2396029} -1)^2+1}\over 2$ is prime (1442553 digits)
 2014-04-05, 17:47 #116 Citrix     Jun 2003 2×33×29 Posts 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?
 2014-04-05, 18:24 #117 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 27×71 Posts 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.  2014-04-05, 18:50 #118 Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100011100000002 Posts 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).
 2014-04-05, 19:15 #119 Citrix     Jun 2003 2×33×29 Posts 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
 2014-04-05, 20:21 #120 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 27×71 Posts 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.
2014-04-06, 00:50   #121
Citrix

Jun 2003

2·33·29 Posts

Quote:
 Originally Posted by Batalov 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post Taiy Hardware 12 2018-01-02 15:54 devarajkandadai Number Theory Discussion Group 11 2017-10-28 20:58 Ammonia Hardware 2 2016-01-21 17:46 CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12 Unregistered Information & Answers 22 2012-03-20 11:38

All times are UTC. The time now is 05:32.

Sat Aug 15 05:32:47 UTC 2020 up 2 days, 2:08, 0 users, load averages: 2.67, 2.79, 2.81