View source for Lucas–Lehmer–Riesel test

{{Short description|Primality test for certain numbers}}
{{more citations needed|date=January 2008}}
In mathematics, the '''Lucas–Lehmer–Riesel test''' is a [[primality test]] for numbers of the form {{math|1=''N'' = ''k'' &middot; 2<sup>''n''</sup> &minus; 1}} with odd {{math|1=''k'' &lt; 2<sup>''n''</sup>}}. The test was developed by [[Hans Riesel]] and it is based on the [[Lucas–Lehmer primality test]]. It is the fastest deterministic algorithm known for numbers of that form.{{Citation needed|date=January 2019}}  For numbers of the form {{math|1=''N'' = ''k'' &middot; 2<sup>''n''</sup> + 1}} ([[Proth number]]s), either application of [[Proth's theorem]] (a [[Las Vegas algorithm]]) or one of the deterministic proofs described in Brillhart–Lehmer–Selfridge 1975<ref name="BLS75">{{ cite journal|first1=John|last1=Brillhart|author-link1=John Brillhart|first2=Derrick Henry|last2=Lehmer|author-link2=Derrick Henry Lehmer|first3=John|last3=Selfridge|author-link3=John Selfridge|title=New Primality Criteria and Factorizations of {{math|1=2<sup>''m''</sup> &pm; 1}}|journal=Mathematics of Computation|volume=29|number=130|date=April 1975|pages=620–647|doi=10.1090/S0025-5718-1975-0384673-1|doi-access=free}}</ref> (see [[Pocklington primality test]]) are used.

==The algorithm==
The algorithm is very similar to the [[Lucas–Lehmer primality test|Lucas–Lehmer test]], but with a variable starting point depending on the value of {{mvar|k}.

Define a sequence {{math|1=''u''<sub>''i''</sub>}} for all {{math|1=''i'' > 0}} by:

: <math>u_i = u_{i-1}^2-2.</math>

Then {{math|1=''N'' = ''k'' &middot; 2<sup>''n''</sup> &minus; 1}}, with {{math|1=''k'' &lt; 2<sup>''n''</sup>}}, is prime if and only if it divides&nbsp;{{math|1=''u''<sub>''n''&minus;2</sub>}}.

==Finding the starting value==
The starting value {{math|1=''u''<sub>0</sub>}} is determined as follows.
* If {{math|1=''k'' ≡ 1 or 5 (mod 6)}}: if {{math|1=1 (mod 6)}} and {{mvar|n}} is even, or {{math|1=5 (mod 6)}} and {{mvar|n}} is odd, then {{math|1=3}} divides {{mvar|N}}, and there is no need to test. Otherwise, {{math|1=N ≡ 7 (mod 24)}} and the [[Lucas sequence]] {{math|1=V(4,1)}} may be used: we take <math>u_0 = (2+\sqrt{3})^k+(2-\sqrt{3})^k</math>, which is the {{mvar|''k''}}th term of that sequence. This is a generalization of the ordinary [[Lucas–Lehmer primality test|Lucas–Lehmer test]], and reduces to it when {{math|1=''k'' = 1}}.
* Otherwise, we are in the case where {{mvar|k}} is a multiple of {{math|1=3}}, and it is more difficult to select the right value of {{math|1=''u''<sub>0</sub>}}. It is known that if {{math|1=''k'' = 3}} and {{math|1=''n'' ≡ 0 or 3 (mod 4)}}, then we can take {{math|1=''u''<sub>0</sub> = 5778}}.

An alternative method for finding the starting value {{math|1=''u''<sub>0</sub>}} is given in Rödseth 1994.<ref name="Rodseth">{{cite journal|last=Rödseth|first=Öystein J.|title=A note on primality tests for {{math|1=''N'' = ''h'' &middot; 2<sup>''n''</sup> − 1}}|journal=BIT Numerical Mathematics|volume=34|number=3|date=1994|pages=451–454|doi=10.1007/BF01935653|s2cid=120438959 |url=http://folk.uib.no/nmaoy/papers/luc.pdf|archive-url=https://web.archive.org/web/20160306082833/http://folk.uib.no/nmaoy/papers/luc.pdf|archive-date=March 6, 2016|url-status=dead}}</ref> The selection method is much easier than that used by Riesel for the 3-divides-{{mvar|k}} case: first, find a {{mvar|P}}-value that satisfies the following equalities of [[Jacobi symbol|Jacobi symbols]]:

:<math>\left(\frac{P-2}{N}\right)=1 \quad\text{and}\quad \left(\frac{P+2}{N}\right)=-1.</math>

In practice, only a few {{mvar|P}}-values need be checked before one is found (5, 8, 9, or 11 work in about 85% of trials).{{citation needed|date=September 2017}}

To find the starting value {{math|1=''u''<sub>0</sub>}} from the {{mvar|P}} value, we can use a  Lucas {{math|1=(''P'',1)}} sequence, as shown in <ref name="Rodseth"/> as well as page 124 of.<ref name="Riesel94">{{cite book | title=Prime Numbers and Computer Methods for Factorization | edition=2nd | first=Hans | last=Riesel | author-link=Hans Riesel | series=Progress in Mathematics | volume=126 | publisher=Birkhäuser | year=1994 | isbn=0-8176-3743-5 | pages=107–121 }}</ref>  The latter explains that when {{math|1=3 &nmid; ''k''}}, {{math|1=''P'' = 4}} may be used as above, and no further search is necessary.

The starting value {{math|1=''u''<sub>0</sub>}} will be the [[Lucas sequence]] term {{math|1=''V''<sub>''k''</sub>(''P'',1)}} taken modulo&nbsp;{{mvar|N}}. This process of selection takes very little time compared to the main test.

==How the test works==
The Lucas–Lehmer–Riesel test is a particular case of group-order primality testing; we demonstrate that some number is prime by showing that some group has the order that it would have were that number prime, and we do this by finding an element of that group of precisely the right order.

For Lucas-style tests on a number {{mvar|N}}, we work in the multiplicative group of a quadratic extension of the integers modulo {{mvar|N}}; if {{mvar|N}} is prime, then the order of this multiplicative group is {{math|1=''N''<sup>2</sup> − 1}}, it has a subgroup of order {{math|1=''N'' + 1}}, and we try to find a generator for that subgroup.

We start off by trying to find a non-iterative expression for the {{math|1=''u''<sub>''i''</sub>}}.  Following the model of the Lucas–Lehmer test, put {{math|1=''u''<sub>''i''</sub> = ''a''<sup>2<sup>''i''</sup></sup> + ''a''<sup>&minus;2<sup>''i''</sup></sup>}}, and by induction we have {{math|1=''u''<sub>''i''</sub> = ''u''{{su|p=2|b=''i''&minus;1}} &minus; 2}}.

So we can consider ourselves as looking at the {{math|1=2<sup>''i''</sup>}}th term of the sequence {{math|1=''v''(''i'') = ''a''<sup>''i''</sup> + ''a''<sup>''i''</sup>}}.  If {{mvar|a}} satisfies a quadratic equation, then this is a Lucas sequence, and has an expression of the form {{math|1=''v''(''i'') = ''&alpha;'' ''v''(''i''&minus;1) + ''&beta;'' ''v''(''i''&minus;2)}}.  Really, we are looking at the {{math|1=''k'' &middot; 2<sup>''i''</sup>}}th term of a different sequence, but since decimations (take every {{mvar|k}}th term starting with the zeroth) of a Lucas sequence are themselves Lucas sequences, we can deal with the factor {{mvar|k}} by picking a different starting point.

==LLR software==
''LLR'' is a program that can run the LLR tests. The program was developed by Jean Penné. Vincent Penné has modified the program so that it can obtain tests via the Internet.<ref>{{cite web|url=https://mersenneforum.org/showthread.php?t=13165|title=LLRnet supports LLR V3.8! (LLRnet2010 V0.73L)|last=Bonath|first=Karsten|date=2010-03-12|work=[[Great Internet Mersenne Prime Search]] forum|access-date=17 November 2021}}</ref> The software is used by both individual prime searchers and some [[distributed computing]] projects including [[Riesel Sieve]] and [[PrimeGrid]].

A revised version, ''LLR2''<ref>{{cite web |url=https://github.com/patnashev/llr2 |title=LLR2 GitHub |first=Pavel |last=Atnashev |website=[[GitHub]] |access-date=2023-11-23}}</ref> was deployed in 2020.<ref>{{cite web |url=https://www.primegrid.com/forum_thread.php?id=9303 |title=LLR2 installed on all big LLR projects |website=PrimeGrid message boards |date=11 September 2020 |access-date=2023-11-23}}</ref>  This generates a "proof of work" certificate which allows the computation to be verified without needing a full double-check.

A further update, ''PRST''<ref>{{cite web |url=https://github.com/patnashev/prst |title=PRST GitHub |first=Pavel |last=Atnashev |website=[[GitHub]] |access-date=2023-11-23}}</ref> uses an alternate certificate scheme<ref>{{cite arXiv |eprint=2209.15623 |class=cs.CR |title=An Efficient Modular Exponentiation Proof Scheme |first1=Darren |last1=Li |first2=Yves |last2=Gallot |date=16 September 2022}}</ref> which takes longer to verify but is faster to generate for some forms of prime.<ref>{{cite web |url=https://www.primegrid.com/forum_thread.php?id=10296 |title=SR5 project switched to PRST |website=PrimeGrid message boards |date=19 July 2023 |access-date=2023-11-23}}</ref>

==See also==
* [[Riesel number]]

==References==
{{reflist}}
*{{cite journal |last=Riesel |first=Hans |year=1969 |title=Lucasian Criteria for the Primality of ''N'' = ''h''·2<sup>''n''</sup>&nbsp;&minus;&nbsp;1 |journal=Mathematics of Computation |volume=23 |issue=108 |pages=869–875 |doi=10.2307/2004975 |jstor= 2004975|publisher=American Mathematical Society }}

==External links==
*[http://jpenne.free.fr/index2.html Download Jean Penné's LLR]
*[https://github.com/danaj/Math-Prime-Util-GMP Math::Prime::Util::GMP] - Part of Perl's ntheory module, this has basic implementations of LLR and Proth form testing, as well as some BLS75 proof methods.

{{Number-theoretic algorithms}}

{{DEFAULTSORT:Lucas-Lehmer-Riesel Test}}
[[Category:Primality tests]]