PFGW 4.0.4 (with gwnum v30.10) Released

[gd_barnes]

Originally Posted by WraithX

PFGW 4.0.6 should not be used. I was trying to help add a feature, but I haven't quite got it working correctly yet. Everyone should avoid PFGW 4.0.6 for now as it will report all inputs as composite. Sorry about this. I'll try to get my new addition fixed soon.

PFGW 4.0.3, 4.0.5, and 4.0.6 should not be used at this point since they cannot properly primality test 12-digit numbers. I haven't seen a 4.0.4.

For versions 4.0.1 and 4.0.2, I sent you a PM with my Email address.

[gd_barnes]

Originally Posted by rogue

I will look into this. I'm not certain what would cause this. For numbers this small it would be using GMP not gwnum for the test.

I did confirm the problem is almost exactly with numbers in the range of 1,000,000,000,000 to 1,100,000,000,000. I ran base R3 for k<1M and had fbncsieve stop at exponent 12 instead of 15. It then found hundreds of "composites" that were actually prime in this specific range.

[rogue]

Originally Posted by gd_barnes

I did confirm the problem is almost exactly with numbers in the range of 1,000,000,000,000 to 1,100,000,000,000. I ran base R3 for k<1M and had fbncsieve stop at exponent 12 instead of 15. It then found hundreds of "composites" that were actually prime in this specific range.

This shouldn't be too hard to track down. I have been waiting from a fix in gwnum before I have a new release.

[WraithX]

Originally Posted by gd_barnes

I did confirm the problem is almost exactly with numbers in the range of 1,000,000,000,000 to 1,100,000,000,000. I ran base R3 for k<1M and had fbncsieve stop at exponent 12 instead of 15. It then found hundreds of "composites" that were actually prime in this specific range.

I didn't look too deeply into the lower bound of this issue, but the upper bound seems to be 2^40 = 1099511627776.

Here are two primes close to 2^40, the one just under is reported "factored", the one just above is reported prime:

> pfgw64 -tp -q"2^40-87"
PFGW Version 4.0.1.64BIT.20191203.Win_Dev [GWNUM 29.8]

Primality testing 2^40-87 [N+1, Brillhart-Lehmer-Selfridge]

2^40-87 is factored (0.0018s+0.0009s)

============================================

> pfgw64 -tp -q"2^40+15"
PFGW Version 4.0.1.64BIT.20191203.Win_Dev [GWNUM 29.8]

Primality testing 2^40+15 [N+1, Brillhart-Lehmer-Selfridge]

Running N+1 test using discriminant 3, base 1+sqrt(3)

Calling Brillhart-Lehmer-Selfridge with factored part 37.50%
2^40+15 is prime! (0.0118s+0.0013s)

Hopefully this helps with troubleshooting.

[a1call]

Originally Posted by gd_barnes

PFGW 4.0.3, 4.0.5, and 4.0.6 should not be used at this point since they cannot properly primality test 12-digit numbers. I haven't seen a 4.0.4.

For versions 4.0.1 and 4.0.2, I sent you a PM with my Email address.

I have been using:

PFGW Version 4.0.4.64BIT.20221214.Win_Dev [GWNUM 30.10]

for PRP testing 2M+ dd candidates. Any ideas if the tests are reliable?

ETA: I will check for some known large primes when I get a chance, but that would likely be the weekend.

[WraithX]

I found the lower bound of this "small prime" problem.

The first misidentified prime is x=999966000317
The last misidentified prime is y=2^40-87 = 1099511627689

The sqrt(x) ~= 999983.000014

So, my current guess is that all numbers less than x are correctly identified since they would have been trial sieved up to 10^6, and the last prime < 10^6 = 10^6-17 = 999983.

It seems like something else takes over when numbers are > 2^40, which thinks that smaller numbers were proven prime, by not being factored to 10^6. So, I believe all PFGW 4.0.1-4.0.5 are fine except for this small range between (10^6-17)^2 and 2^40, ie the problem range is 999966000317 - 1099511627689. Numbers outside of this range should be fine.

a1call, it is not well understood how the roundoff errors during radix conversion issue in GWNUM, with 30.4 <= GWNUM <= 30.11, affects PRP results in PFGW. GWNUM 30.12 fixed that reported issue. And with:

pfgw 4.0.1 - GWNUM 29.8
pfgw 4.0.2 - GWNUM 29.8
pfgw 4.0.3 - GWNUM 29.8
pfgw 4.0.4 - GWNUM 30.10
pfgw 4.0.5 - GWNUM 30.11
pfgw 4.0.6 - (all prp results are incorrect)

The best bet right now is to use PFGW 4.0.1-4.0.3 since they use known good GWNUM libraries.

[a1call]

Acknowledged with many thanks. The only point of ambiguity for me would be 4.0.3 being not recommended in post 573.
I will run my tests when I can.
Again, thank you very much for the heads up.

[gd_barnes]

Originally Posted by a1call

Acknowledged with many thanks. The only point of ambiguity for me would be 4.0.3 being not recommended in post 573.
I will run my tests when I can.
Again, thank you very much for the heads up.

4.0.3 thru 4.0.6 all have the aforementioned problem, which was why I was recommending against them.

In an Email to me, WraithX also confirmed that 4.0.1 and 4.0.2 have the same problem.

I guess they are OK if people know to not run tests on them for 999983^2 < p < 2^40.

I will be running 3.7.7 until we know that all problems are resolved.

[a1call]

Acknowledged with thanks. FTR 4.0.0 has worked for me in the past, and served its purpose.

[rogue]

I have tracked down and fixed the "40 bit" problem with primality testing. This code was changed over a decade ago and only impact terms less than 40 bits in size. I just had to revert part of those changes. In other words this bug has impacted all releases since 2011, which is when that change was made.

I will release a new build of pfgw once George releases an updated gwnum because it has a bug that causes pfgw to crash.

[gd_barnes]

Originally Posted by rogue

I have tracked down and fixed the "40 bit" problem with primality testing. This code was changed over a decade ago and only impact terms less than 40 bits in size. I just had to revert part of those changes. In other words this bug has impacted all releases since 2011, which is when that change was made.

I will release a new build of pfgw once George releases an updated gwnum because it has a bug that causes pfgw to crash.

That's great that you were able to track it down and fix it quickly. Fortunately it wasn't all tests < 40 bits in size that had the problem; it was only ones in the previously discussed narrow range. I suppose if it was all such small tests, it would have been discovered almost immediately.

I wondered why I liked PFGW 3.3.6 from Sept. 2010 so much. I have actually been mostly using that for the last 12+ years for running the CRUS starting bases script and testing other programs. It's what the starting bases script was originally developed from and tested with.

I'm sure 3.3.6 is way less efficient in many ways than up-to-date stuff but I was extremely confident that it had no problems. I recently confirmed that it did not have the 40-bit problem.

...pats self on back for finding a difficult-to-find problem.

...kicks self in butt for not finding sooner what should have been an easy-to-find problem with simple parallel tests on various CRUS bases.

:-)