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

[Batalov]

Now you can do that! ;-)

[Batalov]

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:

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

[Citrix]

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?

[Batalov]

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.

[Batalov]

is prime (1442553 digits)

[Citrix]

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?

[Batalov]

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):

#!/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]

Here is the short test.
Prerequisites:
1. A 32-bit LLR binary (you can try various versions)
2. Use this llr.ini

FacTo=48
TestGM=1
TestGQ=0
PgenInputFile=test1.txt
PgenOutputFile=out1.txt

3. Use this test1.txt

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).

[Citrix]

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?

[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.

[Citrix]

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.

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?