20041202, 16:37  #1 
Jul 2004
Potsdam, Germany
3·277 Posts 
LLRP4 faster than PRP3?
Hi there!
I just started to evaluate LLRP4 Version 3.3 for PSP tests So far, it seems to be nearly 10% faster! (and AFAIK it's a definite Primality test, not a PRobable Prime one...). I currently check whether residues match. Any objections? 
20041202, 18:10  #2 
Jun 2003
3×5×107 Posts 
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 
20041202, 18:29  #3  
Sep 2002
Database er0rr
2^{3}·3·11·17 Posts 
From the readme.txt of llrp4 (30/11/04):
Quote:
Last fiddled with by paulunderwood on 20041202 at 18:30 

20041202, 19:07  #4 
Jul 2004
Potsdam, Germany
3·277 Posts 
Strange... I got differing residues...
PRP3: [Thu Dec 02 19:56:24 2004] 152267*2^1324947+1 is not prime. RES64: 1BC26292A8518641. OLD64: 534727B7F8F492C0 LLRP4: [Thu Dec 02 18:58:36 2004] 152267*2^1324947+1 is not prime. RES64: 041CC4A21A0D2F31 Time: 4353.720 sec. I'll retest the results... 
20041202, 19:17  #5 
Sep 2002
Database er0rr
2^{3}·3·11·17 Posts 
Don't bother LLR uses the LucasLehmerRiesel algorithm for k*2^n1. For k*2^n+1 it uses Proth's Theorem. PRP does a little Fermat test.
http://primes.utm.edu/glossary/page.php?sort=ProthPrime http://primes.utm.edu/glossary/page....sLittleTheorem Last fiddled with by paulunderwood on 20041202 at 19:30 
20050105, 22:00  #6 
Jul 2004
Potsdam, Germany
33F_{16} Posts 
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?

20050105, 22:14  #7 
Jun 2003
3×5×107 Posts 
Not sure what you are trying to ask?
proth test means "prime for sure" fermats little test just means "may be prime" Citrix 
20050105, 23:08  #8 
Jul 2004
Potsdam, Germany
3×277 Posts 
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? 
20050105, 23:21  #9 
Jun 2003
3·5·107 Posts 
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 http://www.utm.edu/research/primes/prove/merged.html Citrix Last fiddled with by Citrix on 20050105 at 23:24 
20050106, 17:38  #10  
May 2004
FRANCE
3·5·41 Posts 
LLR 3.5 (and also LLRP4 3.3) do Proth tests !
Quote:
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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
My CPU is getting faster and faster ;)  lidocorc  Software  2  20081108 09:26 
Faster way to do LLT?  1260  Miscellaneous Math  23  20050904 07:12 
PRP3 segfault with big numbers.  Washuu  Software  6  20050407 17:08 
LLRP4 Version 3.3 now available !  Jean Penné  Software  11  20050120 19:49 
LLR4 and PRP3 bugs  Mystwalker  Prime Sierpinski Project  4  20040917 19:24 