20070309, 08:33  #1 
Dec 2006
Anchorage, Alaska
78_{10} Posts 
Question: PRP and LLR
I'm still a noob (with lots of computing power) at this prime stuff. I'm just curious, what is the difference between proth.exe (PRP) and LLR.exe (LLR)?
I'm just messing around checking out how they work, and I don't know what the difference is between the two. If I was to be looking for a standard k*2^n1 prime, what program would be the choice? Thanks for any info! 
20070309, 12:26  #2 
Mar 2005
Internet; Ukraine, Kiev
11·37 Posts 
Basically, the difference is:
LLR gives you a definite answer: (1) this number is prime or (2) it isn't. PRP can say: (1) this number is definitely composite, or (2) this number is probably prime, but there are still chances that it isn't. Last fiddled with by gribozavr on 20070309 at 12:37 
20070309, 13:53  #3 
May 2004
FRANCE
2×281 Posts 
Note that Yves Gallot's Proth.exe ALSO gives a definite answer! Not to be confused with George Woltman's PRP, which is a probable prime asserting program (but which is very fast).

20070309, 16:13  #4 
Apprentice Crank
Mar 2006
2×227 Posts 
Also, both PRP and LLR are much faster than Gallot's Proth.exe. For n=195,000, I needed about 5 minutes to verify a prime using proth.exe, while the same verification on LLR would have been done in less than 2 minutes.

20070309, 16:41  #5 
Dec 2006
Anchorage, Alaska
2·3·13 Posts 
Oh! Okay!
Hey, thanks for the info. I did a little digging around and came up with some of that, but now everything is clear. Thank you sirs! 
20070309, 17:16  #6 
"Mark"
Apr 2003
Between here and the
2·3·1,031 Posts 
You can perform a primality test on any k*b^n+1 numbers with PFGW, which is built on George's FFT code and is much faster than Proth as well. Primality testing with PFGW is slower than PRP testing with LLR/PRP.
