Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |

**Navigation**

Topics | Register • News • History • How to • Sequences statistics • Template prototypes |

# LLR

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`•2^{n}±`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`< 2^{n}):- Lucas-Lehmer-Riesel algorithm for
`k`•2^{n}-1 numbers. - Proth algorithm for
`k`•2^{n}+1 numbers.

- Lucas-Lehmer-Riesel algorithm for
- for non-base-two numbers (with
`k`<`b`^{n}):`N`-1 Pocklington algorithm for`k`•`b`^{n}+1 numbers.`N`+1 Morrison algorithm for`k`•`b`^{n}-1 numbers.

`k`•`b`^{n}+`c`numbers with |`c`| ≠ 1 or`k`>`b`^{n}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 (2^{p}+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 2^{521}-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