| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "LLR"
(Updating version; tagging variables; improving external links) |
m |
||
| Line 1: | Line 1: | ||
{{InfoboxProgram|title=LLR|workload=primality proving<br/>PRP tests|release=< 2003|latest=3.8.24<br/><small>2020-07-04</small>}} | {{InfoboxProgram|title=LLR|workload=primality proving<br/>PRP tests|release=< 2003|latest=3.8.24<br/><small>2020-07-04</small>}} | ||
| − | '''LLR (Lucas Lehmer Riesel)''' is probably the fastest [[Primality testing program|program]] available to perform primality test on numbers of the form {{Vk}} | + | '''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}}. |
It is written by [[Jean Penné]] and uses the most recent release (29.8) of [[George Woltman]]'s [[gwnum]] library, to do fast multiplications and squarings of large integers modulo {{V|N}}. | It is written by [[Jean Penné]] and uses the most recent release (29.8) of [[George Woltman]]'s [[gwnum]] library, to do fast multiplications and squarings of large integers modulo {{V|N}}. | ||
| Line 16: | Line 16: | ||
**{{V|N}}-1 [[Pocklington algorithm]] for {{Kbn|+|k|b|n}} numbers. | **{{V|N}}-1 [[Pocklington algorithm]] for {{Kbn|+|k|b|n}} numbers. | ||
**{{V|N}}+1 [[Morrison algorithm]] for {{Kbn|k|b|n}} numbers. | **{{V|N}}+1 [[Morrison algorithm]] for {{Kbn|k|b|n}} numbers. | ||
| − | *{{Vk}} | + | *{{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. |
*[[Adleman–Pomerance–Rumely primality test|APR-CL]] primality test for general numbers. | *[[Adleman–Pomerance–Rumely primality test|APR-CL]] primality test for general numbers. | ||
Revision as of 10:55, 25 October 2020
| Workload type | primality proving PRP tests |
| First release | < 2003 |
| Latest version | 3.8.24 2020-07-04 |
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 the most recent release (29.8) 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:
- the fastest algorithms are for base two numbers (with k < 2n):
- Lucas-Lehmer-Riesel algorithm for k•2n-1 numbers.
- Proth algorithm for k•2n+1 numbers.
- for non-base-two numbers (with k < bn):
- N-1 Pocklington algorithm for k•bn+1 numbers.
- N+1 Morrison algorithm for k•bn-1 numbers.
- k•bn+c numbers with |c| ≠ 1 or k > bn can be PRP-tested.
- APR-CL primality test for general numbers.
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
- Main page & Downloads - English and French
- Jean Penné explains the math behind the test at MersenneForum
