Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "LLR"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
(Updating version; fixing link)
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{InfoboxProgram|title=LLR|workload=primality proving<br/>PRP tests|release=< 2003|latest=3.8.21<br/><small>2018-01-28</small>}}
+
{{InfoboxProgram
'''LLR''' is probably the fastest [[Primality testing program|program]] available to perform primality test on numbers of the form k*2<sup>n</sup>±c.
+
|title=LLR
 +
|workload=primality proving<br/>PRP tests
 +
|release=< 2003
 +
|latest=4.0.5<br/><small>2023-11-11</small>
 +
}}
  
It is written by [[Jean Penné]] and uses the most recent release (28.14) of [[George Woltman]]'s [[Gwnums]] library, to do fast multiplications and squarings of large integers modulo N.
+
'''LLR (Lucas Lehmer Riesel)''' is probably the fastest [[Primality testing program|program]] available to perform primality test on numbers of the form {{Vk}}•2<sup>{{Vn}}</sup>±{{V|c}}.
  
LLR can take input file from Paul Jobling's [[NewPGen]] and also from some [[ABC file format|ABC format]] files.
+
It is written by [[Jean Penné]] and uses a recent release (30.11) of [[George Woltman]]'s [[gwnum]] library, to do fast multiplications and squarings of large integers modulo {{V|N}}.
 +
 
 +
LLR can take input files from [[Paul Jobling]]'s [[NewPGen]] and also from some [[ABC file format|ABC format]] files.
  
 
LLR's port for CUDA-based [[GPU]]s is called [[llrCUDA]].
 
LLR's port for CUDA-based [[GPU]]s is called [[llrCUDA]].
Line 10: Line 16:
 
==Algorithms==
 
==Algorithms==
 
Main algorithms:
 
Main algorithms:
*the fastest algorithms are for base two numbers (with k<2<sup>n</sup>):
+
*the fastest algorithms are for base two numbers (with {{Vk}} < 2<sup>{{Vn}}</sup>):
**[[Lucas-Lehmer-Riesel algorithm]] for k&middot;2<sup>n</sup>-1 numbers.
+
**[[Lucas-Lehmer-Riesel algorithm]] for {{Kbn|k|n}} numbers.
**[[Proth algorithm]] for k&middot;2<sup>n</sup>+1 numbers.
+
**[[Proth's theorem|Proth algorithm]] for {{Kbn|+|k|n}} numbers.
*for non-base-two numbers (with k<b<sup>n</sup>):
+
*for non-base-two numbers (with {{Vk}} < {{Vb}}<sup>{{Vn}}</sup>):
**N-1 [[Pocklington algorithm]] for k&middot;b<sup>n</sup>+1 numbers.
+
**{{V|N}}-1 [[Pocklington algorithm]] for {{Kbn|+|k|b|n}} numbers.
**N+1 [[Morrison algorithm]] for k&middot;b<sup>n</sup>-1 numbers.
+
**{{V|N}}+1 [[Morrison algorithm]] for {{Kbn|k|b|n}} numbers.
*k&middot;b<sup>n</sup>+c numbers with |c| <> 1 or k > b<sup>n</sup> can be [[probable prime|PRP]]-tested.
+
*{{Vk}}•{{Vb}}<sup>{{Vn}}</sup>+{{V|c}} numbers with |{{V|c}}| 1 or {{V|k}} > {{Vb}}<sup>{{Vn}}</sup> can be [[probable prime|PRP]]-tested.
*[[APR-CL]] primality test for general numbers.
+
*[[Adleman–Pomerance–Rumely primality test|APR-CL]] primality test for general numbers.
  
Apart from these, the program also implements "special algorithms" for Gaussian-Mersenne norms and Wagstaff numbers (2<sup>p</sup>+1)/3. The latter uses a strong Fermat PRP-test and the [[Vrba-Reix algorithm]].
+
Apart from these, the program also implements "special algorithms" for Gaussian-Mersenne norms and Wagstaff numbers (2<sup>{{V|p}}</sup>+1)/3. The latter uses a strong Fermat PRP-test and the [[Vrba-Reix algorithm]].
  
 
==Usage==
 
==Usage==
Line 28: Line 34:
 
Then running the program with following command:
 
Then running the program with following command:
 
  ./llr64 -d input.abc
 
  ./llr64 -d input.abc
will test 2<sup>521</sup>-1 (M13) for primality with APR-CL test.
+
will test {{Kbn|521}} ([[M13]]) for primality with APR-CL test.
  
 
==External links==
 
==External links==
*[http://jpenne.free.fr/ Main page & Downloads]
+
*Main page & Downloads - [http://jpenne.free.fr/index2.html English] and [http://jpenne.free.fr/ French]
*[http://mersenneforum.org/showthread.php?t=639 Jean Penn&#233; explains the math behind the test] at [[MersenneForum]]
+
*[https://www.mersenneforum.org/showthread.php?t=639 Jean Penné explains the math behind the test] at [[MersenneForum]]
 +
 
 
[[Category:Primality testing program]]
 
[[Category:Primality testing program]]
 +
[[Category:Software]]

Latest revision as of 22:00, 16 December 2023

LLR
Workload type primality proving
PRP tests
First release < 2003
Latest version 4.0.5
2023-11-11

LLR (Lucas Lehmer Riesel) is probably the fastest program available to perform primality test on numbers of the form k•2n±c.

It is written by Jean Penné and uses a recent release (30.11) of George Woltman's gwnum library, to do fast multiplications and squarings of large integers modulo N.

LLR can take input files from Paul Jobling's NewPGen and also from some ABC format files.

LLR's port for CUDA-based GPUs is called llrCUDA.

Algorithms

Main algorithms:

Apart from these, the program also implements "special algorithms" for Gaussian-Mersenne norms and Wagstaff numbers (2p+1)/3. The latter uses a strong Fermat PRP-test and the Vrba-Reix algorithm.

Usage

Example input file input.abc:

ABC $a
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

Then running the program with following command:

./llr64 -d input.abc

will test 2521-1 (M13) for primality with APR-CL test.

External links