Luc-Lehmer-Riesel test

Lucas-Lehmer-Riesel-testet ( LLR ) är ett primalitetstest för tal av formen c (en delmängd av sådana tal kallas Sabit-tal ). Utvecklad av Hans Riesel och baserad på Luc-Lehmer-testet är det den snabbaste deterministiska algoritmen för siffror av detta slag [1] . $N=k\cdot 2^{n}-1$ $2^{n}>k$ $3\cdot 2^{n}-1$

Algoritm

Algoritmen är väldigt lik Luc-Lehmer-testet, men börjar med ett värde som beror på . För algoritmen används Lucas-sekvensen , som ges av formeln: $k$ $\{u_{i}\}$ $i>0$

u_{i}=u_{i-1}^{2}-2

$N$ är primtal om och endast om den delar sig . ${\displaystyle u_{n-2))$

Hitta ett startvärde

fall . Om — är udda, tas värdet . Om , då tas . För en enkel sådan är dessa Mersenne-nummer . $k=1$ $n$ $u_{0}=4$ $n\equiv 3{\pmod {4}}$ $u_{0}=3$ $n$
fall . Värdet kan användas för alla n ≡ 0,3 (mod 4). $k = 3$ $u_{0}=5778$ $n\equiv 0.3{\pmod {4}}$
Om och inte är delbart med 3, kan värdet användas . $k\equiv 1.5{\pmod {6}}$ $N$ $u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}$
I andra fall är det delbart med 3, och att välja rätt startvärde u 0 är mycket svårare. $k$

En alternativ metod för att hitta startvärdet gavs 1994 [2] . Metoden är mycket enklare än den som Riesel använder för fallet när 3 delar . I den alternativa metoden, hitta först värdet som uppfyller följande Jacobi- symbollikhet : $u_{0}$ $k$ $P$

\left({\frac {P-2}{N}}\right)=1

och .

\left({\frac {P+2}{N}}\right)=-1

I praktiken behöver bara ett fåtal värden kontrolleras (5, 8, 9 eller 11 täcker 85%). $P$

För att få det initiala värdet från du kan använda Lucas-sekvensen [2] [3] . För 3 ∤ k (k är inte delbart med 3) kan värdet användas och ingen preliminär sökning behövs. Det initiala värdet är då lika med Lucas-sekvensen modulo . Denna process tar mycket kort tid jämfört med huvudtestet. $u_{0}$ $P$ $(P,1)$ $P=4$ $u_{0}$ $V_{k}(P,1)$ $N$

Mekanism av testet

Luc-Lehmer-Riesel-testet är ett specialfall för att kontrollera enkelheten i ordningen för en grupp. Testet visar att ett visst tal är primtal på grund av att en viss grupp har en ordning som skulle vara lika med detta primtal, för vilken ett element i gruppen identifieras som har exakt den önskade ordningen.

Tester som Lukes tester använder den multiplikativa gruppen av den kvadratiska moduloexpansionen av heltal för ett tal . Om är prime, ordningen för den multiplikativa gruppen är , och den har en undergrupp av ordningen , för testets syfte, söks genereringsmängden för denna undergrupp. $N$ $N$ $N$ $N^{2}-1$ $N+1$

Du kan hitta ett icke-iterativt uttryck för . Efter Lucas-Lehmer-testmodellen ställer vi in och erhåller genom induktion . $u_{i}$ $u_{i}=a^{{2^{i}}}+a^{{-2^{i}}}$ $u_{i}=u_{{i-1}}^{2}-2$

Betrakta det 2 :e elementet i sekvensen . Om a uppfyller en andragradsekvation är det en Lucas-sekvens och lyder uttrycket . Vi letar egentligen efter det -e elementet i en annan sekvens, men eftersom decimering (att välja varje k -:te element) av Lucas-sekvensen också ger en Lucas-sekvens, kan vi välja faktorn k genom att välja en startpunkt. $v(i)=a^{i}+a^{{-i}}$ $v(i)=\alfa v(i-1)+\beta v(i-2)$ $k\ gånger 2^{i}$

LLR-program

LLR är ett program som utför ett LLR-test. Programmet har utvecklats av Jean Penné. Vincent Penné modifierade programmet så att du kan kontrollera ett nummers primeness över Internet. Programmet kan användas både för individuella sökningar, men ingår också i vissa distribuerade datorprojekt inklusive Riesel Sieve och PrimeGrid .

Se även

Rieselnummer

Anteckningar

↑ För att testa primaaliteten hos Proth-tal som liknar dessa - används antingen Proth Theorem ( probabilistisk algoritm ) eller en av de deterministiska algoritmer som beskrevs av Brilhart, Lehmer och Selfridge 1975 - se Brillhart, Lehmer, Selfridge, 1975 $N=k\cdot 2^{n}+1$
↑ 1 2 Rodseth, 1994 .
↑ Riesel, 1994 , sid. 194.

Litteratur

Hans Riesel. Lucasian Criteria for the Primity of N = h •2 n − 1 // Mathematics of Computation. - American Mathematical Society, 1969. - V. 23 , nr. 108 . - S. 869-875 . - doi : 10.2307/2004975 . — .
John Brillhart, Derrick Henry Lehmer, John Selfridge. Nya primäritetskriterier och faktoriseringar av 2^m ± 1 // Mathematics of Computing. - 1975. - Vol. 29. - Fråga. 130 . - S. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
Öystein J. Rodseth. En notering om primärtest för N=h•2^n−1 // BIT Numerisk matematik. - 1994. - T. 34 , nr. 3 . - S. 451-454 . - doi : 10.1007/BF01935653 . Arkiverad från originalet den 4 mars 2016.
Hans Riesel. Primtal och datormetoder för faktorisering. — 2:a. - Birkhäuser, 1994. - T. 126. - S. 107-121. — (Framsteg i matematik). — ISBN 0-8176-3743-5 .

Länkar

Ladda ner Jean Pennes LLR
Math::Prime::Util::GMP — Perl-modul, grundläggande implementering av LLR och Prot-test, och några metoder från Brilhart, Lemaire och Selfridges artikel.