LLR 3.8.0

mdettweiler · 2010-02-09, 22:55

Hi all,

Just now I was checking out the new LLR 3.8.0, and I read in the readme file that it now supports N-1/N+1 primality tests for non-base-2 k*b^n+-1 numbers. Intrigued, I tried running a number pulled from a sieve file off the CRUS website with it, and discovered a couple interesting things:

-LLR now does an N-1/N+1 test by default for non-base-2 numbers; in order to make it run a PRP test as it has before (or like PFGW and Prime95 do), you have to set ForcePRP=1 in llr.ini.

-LLR produces residuals for N-1/N+1 tests, and--lo and behold--they're actually cross-compatible with ones from PRP tests!

As an example:

Code:

193524*15^40001-1 is not prime. RES64: E5EE18918E9340EF. OLD64: 73A7A83B27E1277F Time : 71.309 sec. (LLR doing N+1 test)
193524*15^40001-1 is not prime. RES64: E5EE18918E9340EF. OLD64: 73A7A83B27E1277F Time : 71.299 sec. (LLR doing PRP test)
193524*15^40001-1 is composite: RES64: [E5EE18918E9340EF] (73.4569s+0.0033s) (PFGW doing PRP test)

-N-1/N+1 tests apparently are just as fast as PRP tests, as the above example shows. This is rather surprising, as when PFGW does an N-1/N+1 test, it takes longer than the equivalent PRP test.

Of course, PFGW is still somewhat more useful for conjecture-type efforts due to its greater flexibility when it comes to halting work on a primed k, starting new bases, etc. But nonetheless, LLR's newfound ability to do fast N-1/N+1 tests is quite amazing. I wonder if its optimizations could be integrated into PFGW as well?

Max

rogue · 2010-02-09, 23:24

Quote:

Originally Posted by mdettweiler

Hi all,

Just now I was checking out the new LLR 3.8.0, and I read in the readme file that it now supports N-1/N+1 primality tests for non-base-2 k*b^n+-1 numbers. Intrigued, I tried running a number pulled from a sieve file off the CRUS website with it, and discovered a couple interesting things:

-LLR now does an N-1/N+1 test by default for non-base-2 numbers; in order to make it run a PRP test as it has before (or like PFGW and Prime95 do), you have to set ForcePRP=1 in llr.ini.

-LLR produces residuals for N-1/N+1 tests, and--lo and behold--they're actually cross-compatible with ones from PRP tests!

As an example:

Code:

193524*15^40001-1 is not prime. RES64: E5EE18918E9340EF. OLD64: 73A7A83B27E1277F Time : 71.309 sec. (LLR doing N+1 test)
193524*15^40001-1 is not prime. RES64: E5EE18918E9340EF. OLD64: 73A7A83B27E1277F Time : 71.299 sec. (LLR doing PRP test)
193524*15^40001-1 is composite: RES64: [E5EE18918E9340EF] (73.4569s+0.0033s) (PFGW doing PRP test)

-N-1/N+1 tests apparently are just as fast as PRP tests, as the above example shows. This is rather surprising, as when PFGW does an N-1/N+1 test, it takes longer than the equivalent PRP test.

Of course, PFGW is still somewhat more useful for conjecture-type efforts due to its greater flexibility when it comes to halting work on a primed k, starting new bases, etc. But nonetheless, LLR's newfound ability to do fast N-1/N+1 tests is quite amazing. I wonder if its optimizations could be integrated into PFGW as well?

Max

It is probable that LLR is not doing as much error checking as PFGW. PFGW is also C++ and LLR is straight C, so there could be some C++ overhead in these numbers, but I would be surprised if they had any noticeable impact on the times.

Clearly the N+1 and PRP tests are using the same logic. If LLR were using different logic, then the residues would be different. Could you post a comparison for N-1 as well?

mdettweiler · 2010-02-09, 23:30

Quote:

Originally Posted by rogue

It is probable that LLR is not doing as much error checking as PFGW. PFGW is also C++ and LLR is straight C, so there could be some C++ overhead in these numbers, but I would be surprised if they had any noticeable impact on the times.

Clearly the N+1 and PRP tests are using the same logic. If LLR were using different logic, then the residues would be different. Could you post a comparison for N-1 as well?

Okay, sure:

Code:

95744*39^14789+1 is not prime.  RES64: D38106C2A5EBCDA6.  OLD64: 78D30D4B1603AEEE  Time : 17.420 sec. (LLR doing N-1)
95744*39^14789+1 is not prime.  RES64: D38106C2A5EBCDA6.  OLD64: 78D30D4B1603AEEE  Time : 17.491 sec. (LLR doing PRP)
95744*39^14789+1 is composite: RES64: [D38106C2A5EBCDA6] (17.5283s+0.0016s) (PFGW doing PRP)
95744*39^14789+1 is composite (17.9134s+0.0014s) (PFGW doing N-1)

Seems that N-1 produces compatible residues as well, and the timings are the same. PFGW took a tad longer to do the N-1 test than LLR did, or either took to do the PRP.

Does PFGW do a different amount of error checking by chance for primality tests than it does for PRPs? I know that in the last few versions there have been various changes to how PFGW handles N-1/N+1 primality tests, but as I recall the idea of those taking longer than a PRP test has been around even with much older versions of PFGW--even with the old Proth.exe.

rogue · 2010-02-10, 03:36

I have an open question with Jean regarding the primality proofs he is using. PFGW is clearly using a different proof for N+1 than LLR is.

mdettweiler · 2010-02-12, 06:04

I just noticed something rather interesting about LLR 3.8's N+1 tests. In PFGW, when doing an N-1 or N+1 test, sometimes the test will fail and need to be redone using a different base/discriminant/whatever. This is rather occasional, though definitely not unheard of. However, it seems that when LLR does an N+1 test, it always has to do the test at least a second time, and sometimes even a third. I wonder if this is a side effect of the different N+1 logic it's using?

Note that I haven't tried this with N-1 yet. It may be that this is only an issue with N+1. (FYI, the numbers I tested with were known Riesel base 3 primes around n=25K and Riesel base 37 primes around n=12K.)

At first this got me thinking, does this nullify the speed advantage of doing a fast N+1 test right from the get-go and not having to prove a PRP in a separate step, since it has to do the N+1 test at least twice anyway? Some comparison testing showed that PFGW's N+1 algorithm is significantly slower, enough so that despite having to repeat the test, LLR still usually manages to prove a prime in less time than it would take PFGW to do both a PRP and N+1, so not all is lost.

henryzz · 2010-02-12, 07:23

Quote:

Originally Posted by mdettweiler

I just noticed something rather interesting about LLR 3.8's N+1 tests. In PFGW, when doing an N-1 or N+1 test, sometimes the test will fail and need to be redone using a different base/discriminant/whatever. This is rather occasional, though definitely not unheard of. However, it seems that when LLR does an N+1 test, it always has to do the test at least a second time, and sometimes even a third. I wonder if this is a side effect of the different N+1 logic it's using?

Note that I haven't tried this with N-1 yet. It may be that this is only an issue with N+1. (FYI, the numbers I tested with were known Riesel base 3 primes around n=25K and Riesel base 37 primes around n=12K.)

At first this got me thinking, does this nullify the speed advantage of doing a fast N+1 test right from the get-go and not having to prove a PRP in a separate step, since it has to do the N+1 test at least twice anyway? Some comparison testing showed that PFGW's N+1 algorithm is significantly slower, enough so that despite having to repeat the test, LLR still usually manages to prove a prime in less time than it would take PFGW to do both a PRP and N+1, so not all is lost.

Would LLR's N+1 test detect a composite on the first test a lot of the time?

mdettweiler · 2010-02-12, 07:27

Quote:

Originally Posted by henryzz

Would LLR's N+1 test detect a composite on the first test a lot of the time?

Yes, composites seem to be no problem here--they're always identified as such on the first run, just like with a PRP test.

mdettweiler · 2010-03-02, 23:16

Recently my interest was somewhat piqued by the various new options for different types of PRP tests introduced in LLR 3.8. Its behavior is to:

-Do a deterministic test where possible. For base 2 this means LLR/Proth, for other bases N-1/N+1.
-When a deterministic test is not possible, do a Fermat SPRP test. This is the "regular" PRP test that's used in PFGW, Prime95, and older versions of LLR (and its predecessor, PRP).
-If a Fermat SPRP test comes back positive, do a Lucas/Frobenius PRP test, which is a bit slower but stronger.

I tested on a variety of numbers, using various llr.ini options for force a particular test where applicable. For some of the numbers I ran a particular test more than once to ensure that minor fluctuations didn't throw off the results.

Code:

4436*28^6242-1 is prime! (P = 3)  Time : 4.543 sec. (N+1)
4436*28^6242-1 is prime! (P = 3)  Time : 4.464 sec. (N+1)
4436*28^6242-1 is base 3-Strong Fermat PRP!  Time : 1.458 sec.
4436*28^6242-1 is base 3-Strong Fermat PRP!  Time : 1.466 sec.
4436*28^6242-1 is Frobenius PRP! (P = 5, Q = 2, D = 17)  Time : 4.645 sec.
4436*28^6242-1 is Frobenius PRP! (P = 5, Q = 2, D = 17)  Time : 4.667 sec.
26544*39^19003+1 is composite: RES64: [EFED3590C54BCCC6] (26.4554s+0.0026s) (Fermat PRP w/PFGW)
26544*39^19003+1 is not prime.  RES64: EFED3590C54BCCC6.  OLD64: CFC7A0B24FE3664F  Time : 25.821 sec. (N-1)
26544*39^19003+1 is not prime.  RES64: EFED3590C54BCCC6.  OLD64: CFC7A0B24FE3664F  Time : 25.555 sec. (Fermat PRP)
26544*39^19003+1 is not prime.  RES64: EFED3590C54BCCC6.  OLD64: CFC7A0B24FE3664F  Time : 25.548 sec. (N-1)
26544*39^19003+1 is not prime.  RES64: EFED3590C54BCCC6.  OLD64: CFC7A0B24FE3664F  Time : 25.808 sec. (Fermat PRP)
26544*39^19003+1 is not prime(P = 5, Q = 2), Lucas RES64: 74F99745043CDEBC  Time : 65.720 sec. (Frobenius PRP)
138876*39^19002+1 is Frobenius PRP! (P = 4, Q = 2, D = 8)  Time : 90.798 sec.
138876*39^19002+1 is prime!  Time : 25.824 sec. (N-1)

First of all, I tried a known base 28 prime with all the applicable methods. With an N+1 test it took somewhat longer than a Fermat PRP did, which is to be expected since while LLR's N-1/N+1 method is just as fast as Fermat PRP for composites, for primes it has to do some additional steps. The Frobenius PRP is in a similar boat; it's multistep on primes and thus winds up being slower than either the N+1 or Fermat PRP.

The second number is a known composite base 39 number. As expected, the N-1 and Fermat PRP took the same amount of time. (I also included a Fermat PRP from PFGW for reference.) The Frobenius PRP (well, actually just a Lucas PRP in this case, since the Frobenius part of the Lucas-Frobenius method is only applied for numbers that pass the apparently weaker Lucas PRP test) took somewhat longer; for composites it's not multistep, but the Lucas PRP test is significantly slower than the Fermat PRP or N-1 methods.

The third is a known prime on base 39, of approximatley the same size as the second number. As you can see, the addition of the Frobenius test makes it take about 25 seconds longer than a comparable Lucas-only test on the similarly-sized composite. But that's nothing compared to the blisteringly fast N-1 test for this number: it finished in about the same time as a comparable Fermat PRP did!

That's improbable, but not impossible; the nature of the N-1 and N+1 tests is such that for primes, sometimes they have to be retried with another base, and while LLR needs to retry a lot more than PFGW (to the extent that it almost always needs to retry at least once), occasionally it doesn't. Perhaps this isn't therefore the best representative of the time it takes to do an N-1 test, but nonetheless the picture of how the timings of these tests is probably pretty clear from the results on other tests.

2010-02-09, 22:55	#1
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3·2,083 Posts	LLR 3.8.0 Hi all, Just now I was checking out the new LLR 3.8.0, and I read in the readme file that it now supports N-1/N+1 primality tests for non-base-2 kb^n+-1 numbers. Intrigued, I tried running a number pulled from a sieve file off the CRUS website with it, and discovered a couple interesting things: -LLR now does an N-1/N+1 test by default for non-base-2 numbers; in order to make it run a PRP test as it has before (or like PFGW and Prime95 do), you have to set ForcePRP=1 in llr.ini. -LLR produces residuals for N-1/N+1 tests, and--lo and behold--they're actually cross-compatible with ones from PRP tests! As an example: Code: 19352415^40001-1 is not prime. RES64: E5EE18918E9340EF. OLD64: 73A7A83B27E1277F Time : 71.309 sec. (LLR doing N+1 test) 19352415^40001-1 is not prime. RES64: E5EE18918E9340EF. OLD64: 73A7A83B27E1277F Time : 71.299 sec. (LLR doing PRP test) 19352415^40001-1 is composite: RES64: [E5EE18918E9340EF] (73.4569s+0.0033s) (PFGW doing PRP test) -N-1/N+1 tests apparently are just as fast as PRP tests, as the above example shows. This is rather surprising, as when PFGW does an N-1/N+1 test, it takes longer than the equivalent PRP test. Of course, PFGW is still somewhat more useful for conjecture-type efforts due to its greater flexibility when it comes to halting work on a primed k, starting new bases, etc. But nonetheless, LLR's newfound ability to do fast N-1/N+1 tests is quite amazing. I wonder if its optimizations could be integrated into PFGW as well? Max

2010-02-10, 03:36	#4
rogue "Mark" Apr 2003 Between here and the 2⁴×397 Posts	I have an open question with Jean regarding the primality proofs he is using. PFGW is clearly using a different proof for N+1 than LLR is. Last fiddled with by rogue on 2010-02-10 at 03:36

2010-02-12, 06:04	#5
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3·2,083 Posts	I just noticed something rather interesting about LLR 3.8's N+1 tests. In PFGW, when doing an N-1 or N+1 test, sometimes the test will fail and need to be redone using a different base/discriminant/whatever. This is rather occasional, though definitely not unheard of. However, it seems that when LLR does an N+1 test, it always has to do the test at least a second time, and sometimes even a third. I wonder if this is a side effect of the different N+1 logic it's using? Note that I haven't tried this with N-1 yet. It may be that this is only an issue with N+1. (FYI, the numbers I tested with were known Riesel base 3 primes around n=25K and Riesel base 37 primes around n=12K.) At first this got me thinking, does this nullify the speed advantage of doing a fast N+1 test right from the get-go and not having to prove a PRP in a separate step, since it has to do the N+1 test at least twice anyway? Some comparison testing showed that PFGW's N+1 algorithm is significantly slower, enough so that despite having to repeat the test, LLR still usually manages to prove a prime in less time than it would take PFGW to do both a PRP and N+1, so not all is lost. Last fiddled with by mdettweiler on 2010-02-12 at 06:05

2010-03-02, 23:16	#8
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3×2,083 Posts	Recently my interest was somewhat piqued by the various new options for different types of PRP tests introduced in LLR 3.8. Its behavior is to: -Do a deterministic test where possible. For base 2 this means LLR/Proth, for other bases N-1/N+1. -When a deterministic test is not possible, do a Fermat SPRP test. This is the "regular" PRP test that's used in PFGW, Prime95, and older versions of LLR (and its predecessor, PRP). -If a Fermat SPRP test comes back positive, do a Lucas/Frobenius PRP test, which is a bit slower but stronger. I tested on a variety of numbers, using various llr.ini options for force a particular test where applicable. For some of the numbers I ran a particular test more than once to ensure that minor fluctuations didn't throw off the results. Code: 443628^6242-1 is prime! (P = 3) Time : 4.543 sec. (N+1) 443628^6242-1 is prime! (P = 3) Time : 4.464 sec. (N+1) 443628^6242-1 is base 3-Strong Fermat PRP! Time : 1.458 sec. 443628^6242-1 is base 3-Strong Fermat PRP! Time : 1.466 sec. 443628^6242-1 is Frobenius PRP! (P = 5, Q = 2, D = 17) Time : 4.645 sec. 443628^6242-1 is Frobenius PRP! (P = 5, Q = 2, D = 17) Time : 4.667 sec. 2654439^19003+1 is composite: RES64: [EFED3590C54BCCC6] (26.4554s+0.0026s) (Fermat PRP w/PFGW) 2654439^19003+1 is not prime. RES64: EFED3590C54BCCC6. OLD64: CFC7A0B24FE3664F Time : 25.821 sec. (N-1) 2654439^19003+1 is not prime. RES64: EFED3590C54BCCC6. OLD64: CFC7A0B24FE3664F Time : 25.555 sec. (Fermat PRP) 2654439^19003+1 is not prime. RES64: EFED3590C54BCCC6. OLD64: CFC7A0B24FE3664F Time : 25.548 sec. (N-1) 2654439^19003+1 is not prime. RES64: EFED3590C54BCCC6. OLD64: CFC7A0B24FE3664F Time : 25.808 sec. (Fermat PRP) 2654439^19003+1 is not prime(P = 5, Q = 2), Lucas RES64: 74F99745043CDEBC Time : 65.720 sec. (Frobenius PRP) 13887639^19002+1 is Frobenius PRP! (P = 4, Q = 2, D = 8) Time : 90.798 sec. 13887639^19002+1 is prime! Time : 25.824 sec. (N-1) First of all, I tried a known base 28 prime with all the applicable methods. With an N+1 test it took somewhat longer than a Fermat PRP did, which is to be expected since while LLR's N-1/N+1 method is just as fast as Fermat PRP for composites, for primes it has to do some additional steps. The Frobenius PRP is in a similar boat; it's multistep on primes and thus winds up being slower than either the N+1 or Fermat PRP. The second number is a known composite base 39 number. As expected, the N-1 and Fermat PRP took the same amount of time. (I also included a Fermat PRP from PFGW for reference.) The Frobenius PRP (well, actually just a Lucas PRP in this case, since the Frobenius part of the Lucas-Frobenius method is only applied for numbers that pass the apparently weaker Lucas PRP test) took somewhat longer; for composites it's not multistep, but the Lucas PRP test is significantly slower than the Fermat PRP or N-1 methods. The third is a known prime on base 39, of approximatley the same size as the second number. As you can see, the addition of the Frobenius test makes it take about 25 seconds longer than a comparable Lucas-only test on the similarly-sized composite. But that's nothing compared to the blisteringly fast N-1 test for this number: it finished in about the same time as a comparable Fermat PRP did! That's improbable, but not impossible; the nature of the N-1 and N+1 tests is such that for primes, sometimes they have to be retried with another base, and while LLR needs to retry a lot more than PFGW (to the extent that it almost always needs to retry at least once), occasionally it doesn't. Perhaps this isn't therefore the best representative of the time it takes to do an N-1 test, but nonetheless the picture of how the timings of these tests is probably pretty clear from the results on other tests.