LLRP4 faster than PRP3?

Mystwalker · 2004-12-02, 16:37

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?

Citrix · 2004-12-02, 18:10

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

paulunderwood · 2004-12-02, 18:29

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 !).

Mystwalker · 2004-12-02, 19:07

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...

paulunderwood · 2004-12-02, 19:17

Don't bother

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.

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

http://primes.utm.edu/glossary/page....sLittleTheorem

Mystwalker · 2005-01-05, 22:00

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?

Citrix · 2005-01-05, 22:14

Not sure what you are trying to ask?

proth test means "prime for sure"

fermats little test just means "may be prime"

Citrix

Mystwalker · 2005-01-05, 23:08

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?

Citrix · 2005-01-05, 23:21

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

Jean Penné · 2005-01-06, 17:38

Quote:

Originally Posted by 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

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

Citrix

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

2004-12-02, 16:37	#1
Mystwalker 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?

2004-12-02, 19:17	#5
paulunderwood Sep 2002 Database er0rr 2³·3·11·17 Posts	Don't bother LLR uses the Lucas-Lehmer-Riesel algorithm for k2^n-1. For k2^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 2004-12-02 at 19:30

2005-01-05, 23:21	#9
Citrix 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 2005-01-05 at 23:24

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

2004-12-02, 18:10	#2
Citrix 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

2004-12-02, 19:07	#4
Mystwalker Jul 2004 Potsdam, Germany 3·277 Posts	Strange... I got differing residues... PRP3: [Thu Dec 02 19:56:24 2004] 1522672^1324947+1 is not prime. RES64: 1BC26292A8518641. OLD64: 534727B7F8F492C0 LLRP4: [Thu Dec 02 18:58:36 2004] 1522672^1324947+1 is not prime. RES64: 041CC4A21A0D2F31 Time: 4353.720 sec. I'll retest the results...

2005-01-05, 22:00	#6
Mystwalker Jul 2004 Potsdam, Germany 33F₁₆ 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?

2005-01-05, 22:14	#7
Citrix 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

2005-01-05, 23:08	#8
Mystwalker 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?