# LLR

Workload type |
primality proving PRP tests |

First release |
< 2003 |

Latest version |
3.8.21 2018-01-28 |

**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 (28.14) of George Woltman's Gwnums library, to do fast multiplications and squarings of large integers modulo N.

LLR can take input file 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 k·2
- 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.

- N-1 Pocklington algorithm for k·b
- 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.