Yet another LLR bug - Page 2

ATH · 2011-03-02, 02:33

Crashed for me as well on Windows 7 64bit Q9450 and Windows XP 32 bit Pentium 4 with the 32 bit binary from: http://jpenne.free.fr/index2.html

Just make a worktodo.txt with these 2 lines:
ABC$a*$b^$c$d
5 10 19737 3

and llr.ini with this:
PgenInputFile=worktodo.txt
Verbose=1

It passes the SPRP test but crashes as soon as Lucas test starts.

rogue · 2011-03-02, 04:03

Quote:

Originally Posted by Prime95

Ugh, I cannot reproduce in Prime95 using my QA code that calls every gwnum routine.

I did download and compile the LLR source, but don't know how to use it. Can you upload an input file that exhibits the problem? Thanks.

What I'll try to do is reproduce the string of calls to gwnum routines that can produce the error in a small program. That would make it much easier for you to debug.

Prime95 · 2011-03-02, 05:41

It looks like the problem is a call to gwsetaddin.

The gwnum.h include file states that you can only use this routine if abs(c) = 1.

Jean Penné · 2011-03-02, 06:32

Quote:

Originally Posted by Prime95

It looks like the problem is a call to gwsetaddin.

The gwnum.h include file states that you can only use this routine if abs(c) = 1.

Hi George, Mark et al,

I knew that, and used a gwsub3 in place but, alas... "to be sure", I still used gwsetaddin(gwdata, 0) to reset the addin constant to zero!! I thought this night that it could be the cause of the crash, and that is true!

George and me found the bug almost simultaneously... But I am sorry for having wrongly worried you about that...

I shall release the fixed development version soon.

Best Regards,
Jean

Jean Penné · 2011-03-02, 16:03

Hi George,

In this 3.8.5 development version, I implement the BPSW PRP test (see http://www.trnicely.net/misc/bpsw.html). In this test, the Q parameter may be negative, and then the following Frobenius test gives a wrong result if I use setmulbyconst (gwdata, Q)... This is not grave because I get the good result when multiplying by N+Q after the squaring, but perhaps it would be better to indicate this restriction in the gwnum.h file ?

- Results using setmulbyconst :

Starting probable prime test of 10^500+961
Using all-complex FFT length 192, a = 2
10^500+961 is base 2-Strong Fermat PRP! Time : 114.884 ms.
Starting Lucas sequence
Using all-complex FFT length 192, P = 1, Q = -3
10^500+961 is strong-Fermat and BPSW PRP, Starting Frobenius test sequence
Using all-complex FFT length 192, Q = -3
10^500+961 is strong-Fermat and BPSW PSP (P = 1, Q = -3), but composite!!. Frobenius RES64: 3740D82555AE273E Time : 72.012 ms.

Result using gwsafemul(gwdata, gwQ, x) after the squaring of x :

Starting probable prime test of 10^500+961
Using all-complex FFT length 192, a = 2
10^500+961 is base 2-Strong Fermat PRP! Time : 33.443 ms.
Starting Lucas sequence
Using all-complex FFT length 192, P = 1, Q = -3
10^500+961 is strong-Fermat and BPSW PRP, Starting Frobenius test sequence
Using all-complex FFT length 192, Q = -3
10^500+961 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = -3, D = 13) Time : 72.379 ms.

Best Regards,
Jean

Prime95 · 2011-03-02, 17:02

Quote:

Originally Posted by Jean Penné

Frobenius test gives a wrong result if I use setmulbyconst (gwdata, Q)... This is not grave because I get the good result when multiplying by N+Q after the squaring, but perhaps it would be better to indicate this restriction in the gwnum.h file ?

Odd. I looked at the code at I don't see anything that precludes using a negative mulbyconst. I then added a check to my QA code and I didn't run into any problems.

I may need to download your development version to debug this.

Jean Penné · 2011-03-02, 21:48

Quote:

Originally Posted by Prime95

Odd. I looked at the code at I don't see anything that precludes using a negative mulbyconst. I then added a check to my QA code and I didn't run into any problems.

I may need to download your development version to debug this.

Hi,

You may download the source now from my development directory :

http://jpenne.free.fr/Development/llr385devsrc.zip

Please note it is not-at-all a stable version...

- The problematic code is in "commonFrobeniusPRP" function.

- Here is the problematic test (using gwsetmulbyconst) :

>cllr -oDebug=1 -oBPSW=1 -d -q"10^500+961"
Starting probable prime test of 10^500+961
Using all-complex FFT length 192, a = 2
10^500+961 is base 2-Strong Fermat PRP! Time : 1.532 sec.
Starting Lucas sequence
Using all-complex FFT length 192, P = 1, Q = -3
10^500+961 is strong-Fermat and BPSW PRP, Starting Frobenius test sequence
Using all-complex FFT length 192, Q = -3
10^500+961 is strong-Fermat and BPSW PSP (P = 1, Q = -3), but composite!!. Frobenius RES64: 3740D82555AE273E Time : 3.876 sec.

- Here is the successful test (using gwsafemul) :

>cllr -oDebug=0 -oBPSW=1 -d -q"10^500+961"
Starting probable prime test of 10^500+961
Using all-complex FFT length 192, a = 2
10^500+961 is base 2-Strong Fermat PRP! Time : 1.881 sec.
Starting Lucas sequence
Using all-complex FFT length 192, P = 1, Q = -3
10^500+961 is strong-Fermat and BPSW PRP, Starting Frobenius test sequence
Using all-complex FFT length 192, Q = -3
10^500+961 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = -3, D = 13) Time : 5.063 sec.

I made also these tests while displaying the 64 bit residues of the 10 first iterations, and saw that the residues differ as soon as after the first one!

Thank you for your help and Best Regards,
Jean

Prime95 · 2011-03-04, 01:27

The bug is in gianttogw for non-base-2 numbers.

If testing 10^500+n, then the numbers from 10^500 to 10^500+n-1 are not converted properly. Attached is a corrected gwnum.c. You can use it until I put together a 25.6 release.

gwsetmulbyconst does work with negative numbers.

Jean Penné · 2011-03-04, 06:28

Quote:

Originally Posted by Prime95

The bug is in gianttogw for non-base-2 numbers.

If testing 10^500+n, then the numbers from 10^500 to 10^500+n-1 are not converted properly. Attached is a corrected gwnum.c. You can use it until I put together a 25.6 release.

gwsetmulbyconst does work with negative numbers.

Thank you very much George!

But it is surprising! How can I get the correct result starting with a false converted value?? What a subtil bug....

Also, I cannot find here the attached corrected code, but it is not urgent...

About the previous problem (the crash) : In the future, I would study more carefully the gwnum's specifications before using it...

Best Regards,
Jean

Prime95 · 2011-03-04, 15:04

Quote:

Originally Posted by Jean Penné

Also, I cannot find here the attached corrected code

My bad. Trying again.

Jean Penné · 2011-03-04, 19:00

Quote:

Originally Posted by Prime95

My bad. Trying again.

Well received and tested, this time it works (with different intermediate residues).

(MAX_AUXILIARY_THREADS was not defined, I have defined it to 10, in order to make the build possible)

Thanks again and Best Regards,
Jean

2011-03-02, 02:33	#12
ATH Einyen Dec 2003 Denmark BBF₁₆ Posts	Crashed for me as well on Windows 7 64bit Q9450 and Windows XP 32 bit Pentium 4 with the 32 bit binary from: http://jpenne.free.fr/index2.html Just make a worktodo.txt with these 2 lines: ABC$a$b^$c$d 5 10 19737 3 and llr.ini with this: PgenInputFile=worktodo.txt Verbose=1 It passes the SPRP test but crashes as soon as Lucas test starts. Last fiddled with by ATH on 2011-03-02 at 02:34*

2011-03-02, 16:03	#16
Jean Penné May 2004 FRANCE 562₁₀ Posts	Nevertheless, yet another (benign) problem... Hi George, In this 3.8.5 development version, I implement the BPSW PRP test (see http://www.trnicely.net/misc/bpsw.html). In this test, the Q parameter may be negative, and then the following Frobenius test gives a wrong result if I use setmulbyconst (gwdata, Q)... This is not grave because I get the good result when multiplying by N+Q after the squaring, but perhaps it would be better to indicate this restriction in the gwnum.h file ? - Results using setmulbyconst : Starting probable prime test of 10^500+961 Using all-complex FFT length 192, a = 2 10^500+961 is base 2-Strong Fermat PRP! Time : 114.884 ms. Starting Lucas sequence Using all-complex FFT length 192, P = 1, Q = -3 10^500+961 is strong-Fermat and BPSW PRP, Starting Frobenius test sequence Using all-complex FFT length 192, Q = -3 10^500+961 is strong-Fermat and BPSW PSP (P = 1, Q = -3), but composite!!. Frobenius RES64: 3740D82555AE273E Time : 72.012 ms. Result using gwsafemul(gwdata, gwQ, x) after the squaring of x : Starting probable prime test of 10^500+961 Using all-complex FFT length 192, a = 2 10^500+961 is base 2-Strong Fermat PRP! Time : 33.443 ms. Starting Lucas sequence Using all-complex FFT length 192, P = 1, Q = -3 10^500+961 is strong-Fermat and BPSW PRP, Starting Frobenius test sequence Using all-complex FFT length 192, Q = -3 10^500+961 is strong-Fermat, BPSW and Frobenius PRP! (P = 1, Q = -3, D = 13) Time : 72.379 ms. Best Regards, Jean

2011-03-02, 05:41	#14
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2·7·521 Posts	It looks like the problem is a call to gwsetaddin. The gwnum.h include file states that you can only use this routine if abs(c) = 1.

2011-03-04, 01:27	#19
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2·7·521 Posts	The bug is in gianttogw for non-base-2 numbers. If testing 10^500+n, then the numbers from 10^500 to 10^500+n-1 are not converted properly. Attached is a corrected gwnum.c. You can use it until I put together a 25.6 release. gwsetmulbyconst does work with negative numbers.