mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Sierpinski Project

Reply
 
Thread Tools
Old 2004-12-02, 16:37   #1
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Thumbs up 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?
Mystwalker is offline   Reply With Quote
Old 2004-12-02, 18:10   #2
Citrix
 
Citrix's Avatar
 
Jun 2003

3×5×107 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2004-12-02, 18:29   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·11·17 Posts
Default

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

Last fiddled with by paulunderwood on 2004-12-02 at 18:30
paulunderwood is offline   Reply With Quote
Old 2004-12-02, 19:07   #4
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Default

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...
Mystwalker is offline   Reply With Quote
Old 2004-12-02, 19:17   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·11·17 Posts
Default

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

Last fiddled with by paulunderwood on 2004-12-02 at 19:30
paulunderwood is offline   Reply With Quote
Old 2005-01-05, 22:00   #6
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

33F16 Posts
Default

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?
Mystwalker is offline   Reply With Quote
Old 2005-01-05, 22:14   #7
Citrix
 
Citrix's Avatar
 
Jun 2003

3×5×107 Posts
Default

Not sure what you are trying to ask?

proth test means "prime for sure"

fermats little test just means "may be prime"

Citrix
Citrix is offline   Reply With Quote
Old 2005-01-05, 23:08   #8
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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?
Mystwalker is offline   Reply With Quote
Old 2005-01-05, 23:21   #9
Citrix
 
Citrix's Avatar
 
Jun 2003

3·5·107 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-01-06, 17:38   #10
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

3·5·41 Posts
Default LLR 3.5 (and also LLRP4 3.3) do Proth tests !

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
Jean Penné is online now   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 07:50.


Tue Jan 31 07:50:18 UTC 2023 up 166 days, 5:18, 0 users, load averages: 0.92, 0.96, 1.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔