LLRP4 faster than PRP3?
 

Hi there!

I just started to evaluate [url=http://www.mersenneforum.org/showthread.php?t=3356]LLRP4 Version 3.3[/url] for PSP tests
So far, it seems to be nearly 10% faster! :banana: (and AFAIK it's a definite Primality test, not a PRobable Prime one...).

I currently check whether residues match. Any objections?

LLR4 uses the same algorithm as PRP for proth numbers, so sorry, but LLR also uses a probable prime test not a definitive one.

Citrix
:cool: :cool: :cool:

From the readme.txt of llrp4 (30/11/04):

[QUOTE]Version 3.3 :



-This new version can now also prove the primality of k*2^n+1 numbers !

Thanks to the new George Woltman's "Gwnums" and assembler code, to implement the Proth theorem algorithm in this program was almost straightforward. Moreover, the performances of these tests seem to be even better than those of the Lucas-Lehmer-Riesel ones.

I tested successfully this new feature on all the verified Proth primes extracted from the Chris Caldwell's database (more than 38,000 primes !).[/QUOTE]

Strange... I got differing residues...

PRP3:
[Thu Dec 02 19:56:24 2004]
152267*2^1324947+1 is not prime. [b]RES64: 1BC26292A8518641[/b]. OLD64: 534727B7F8F492C0

LLRP4:
[Thu Dec 02 18:58:36 2004]
152267*2^1324947+1 is not prime. [b]RES64: 041CC4A21A0D2F31[/b] Time: 4353.720 sec.

I'll retest the results...

Don't bother :no: LLR uses the Lucas-Lehmer-Riesel algorithm for k*2^n-1. For k*2^n+1 it uses Proth's Theorem. PRP does a little Fermat test.

[url]http://primes.utm.edu/glossary/page.php?sort=ProthPrime[/url]

[url]http://primes.utm.edu/glossary/page.php?sort=FermatsLittleTheorem[/url]

The Prime Pages don't mention Proth's Theorem to produce probable primes (contrary to the "little Fermat test" entry) - so are all positives of this theorem definitely primes?

Not sure what you are trying to ask?

proth test means "prime for sure"

fermats little test just means "may be prime"

Citrix
:cool: :cool: :cool:

That's exactly what I was asking for, thanks!

So my assumption in the thread opening posting ("and AFAIK it's a definite Primality test, not a PRobable Prime one...") is correct, isn't it?

As far as I remember that LLR uses fermats little test not proth's test. so it doesn't proove prime for sure.

I haven't looked at the source of LLR4, so I can't say if a change was made.

Secondly, the run time for a proth test is the same as the run time for a fermats little test. What I don't know is that why some one would implement the fermats little test and not the proth test to test all the numbers that are PRP in the same software.

See

[url]http://www.utm.edu/research/primes/prove/merged.html[/url]

Citrix
:cool: :cool: :cool:

LLR 3.5 (and also LLRP4 3.3) do Proth tests !
 

[QUOTE=Citrix]As far as I remember that LLR uses fermats little test not proth's test. so it doesn't proove prime for sure.

I haven't looked at the source of LLR4, so I can't say if a change was made.

Secondly, the run time for a proth test is the same as the run time for a fermats little test. What I don't know is that why some one would implement the fermats little test and not the proth test to test all the numbers that are PRP in the same software.

See

[url]http://www.utm.edu/research/primes/prove/merged.html[/url]

Citrix
:cool: :cool: :cool:[/QUOTE]

From Version 3.3, LLRP4 and now, LLR Version 3.5 (which runs on all PC's)
use really the Proth theorem algorithm to test the k*2^n+1 numbers, so, a
positive result from the test means that the number is prime, and not only
PRP ! This is explained in the attached Readme.txt file.
Regards,
Jean