Luc-Lehmer-Riesel test

Lucas-Lehmer-Riesel-testen ( LLR ) er en primalitetstest for tal af formen c (en delmængde af sådanne tal kaldes Sabit-tal ). Udviklet af Hans Riesel og baseret på Luc-Lehmer-testen , er det den hurtigste deterministiske algoritme for tal af denne art [1] . $N=k\cdot 2^{n}-1$ $2^{n}>k$ $3\cdot 2^{n}-1$

Algoritme

Algoritmen minder meget om Luc-Lehmer-testen, men starter med en værdi, der afhænger af . Til algoritmen bruges Lucas-sekvensen , som er givet ved formlen: $k$ $\{u_{i}\}$ $i>0$

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

$N$ er prime, hvis og kun hvis den deler sig . ${\displaystyle u_{n-2))$

Find en startværdi

sag . Hvis — er ulige, tages værdien . Hvis , så er taget . For en simpel en er disse Mersenne-tal . $k=1$ $n$ $u_{0}=4$ $n\equiv 3{\pmod {4}}$ $u_{0}=3$ $n$
sag . Værdien kan bruges for alle n ≡ 0,3 (mod 4). $k = 3$ $u_{0}=5778$ $n\equiv 0.3{\pmod {4}}$
Hvis og ikke er deleligt med 3, kan værdien bruges . $k\equiv 1.5{\pmod {6}}$ $N$ $u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}$
I andre tilfælde er den delelig med 3, og det er meget vanskeligere at vælge den korrekte startværdi u 0 . $k$

En alternativ metode til at finde startværdien blev givet i 1994 [2] . Metoden er meget enklere end den, Riesel bruger til tilfældet, hvor 3 deler . I den alternative metode skal du først finde den værdi , der opfylder følgende Jacobi-symbollighed : $u_{0}$ $k$ $P$

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

og .

\venstre({\frac {P+2}{N}}\højre)=-1

I praksis er det kun nogle få værdier, der skal kontrolleres (5, 8, 9 eller 11 dækker 85%). $P$

For at få startværdien fra kan du bruge Lucas-sekvensen [2] [3] . For 3 ∤ k (k er ikke deleligt med 3), kan værdien bruges, og der er ikke behov for et foreløbigt opslag. Startværdien er så lig med Lucas-sekvensen modulo . Denne proces tager meget kort tid sammenlignet med hovedtesten. $u_{0}$ $P$ $(P,1)$ $P=4$ $u_{0}$ $V_{k}(P,1)$ $N$

Testens mekanisme

Luc-Lehmer-Riesel-testen er et særligt tilfælde af kontrol af enkelheden i rækkefølgen af en gruppe. Testen viser, at et bestemt tal er primtal på grund af det faktum, at en bestemt gruppe har en rækkefølge, der ville være lig med dette primtal, for hvilket der identificeres et element i gruppen, som har præcis den ønskede rækkefølge.

Tests som Luke's tests bruger den multiplikative gruppe af den kvadratiske modulo-udvidelse af heltal for et tal . Hvis er prime, rækkefølgen af den multiplikative gruppe er , og den har en undergruppe af orden , med henblik på testen søges genereringssættet for denne undergruppe. $N$ $N$ $N$ $N^{2}-1$ $N+1$

Du kan finde et ikke-iterativt udtryk for . Efter Lucas-Lehmer-testmodellen indstiller og opnår vi ved induktion . $u_{i}$ $u_{i}=a^{{2^{i}}}+a^{{-2^{i}}}$ $u_{i}=u_{{i-1}}^{2}-2$

Overvej det 2 i -te element i sekvensen . Hvis a opfylder en andengradsligning, er det en Lucas-sekvens og adlyder udtrykket . Vi leder faktisk efter det -te element i en anden sekvens, men da decimering (valg af hvert k -te element) af Lucas-sekvensen også giver en Lucas-sekvens, kan vi vælge faktoren k ved at vælge et udgangspunkt. $v(i)=a^{i}+a^{{-i}}$ $v(i)=\alfa v(i-1)+\beta v(i-2)$ $k\ gange 2^{i}$

LLR-program

LLR er et program, der udfører en LLR-test. Programmet er udviklet af Jean Penné. Vincent Penné ændrede programmet, så du kan tjekke et tals primehed over internettet. Programmet kan bruges både til individuelle søgninger, men er også inkluderet i nogle distribuerede computerprojekter , herunder Riesel Sieve og PrimeGrid .

Se også

Riesel tal

Noter

↑ For at teste primaliteten af Proth-tal, der ligner disse - bruges enten Proth -sætningen ( sandsynlighedsalgoritme ) eller en af de deterministiske algoritmer beskrevet af Brilhart, Lehmer og Selfridge i 1975 - se Brillhart, Lehmer, Selfridge, 1975 $N=k\cdot 2^{n}+1$
↑ 1 2 Rodseth, 1994 .
↑ Riesel, 1994 , s. 194.

Litteratur

Hans Riesel. Lucasiske kriterier for Primalitet af N = h •2 n − 1 // Mathematics of Computing. - American Mathematical Society, 1969. - V. 23 , no. 108 . - S. 869-875 . - doi : 10.2307/2004975 . — .
John Brillhart, Derrick Henry Lehmer, John Selfridge. Nye Primalitetskriterier og Faktoriseringer på 2^m ± 1 // Beregningsmatematik. - 1975. - Bd. 29. - Udgave. 130 . - S. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
Öystein J. Rodseth. En note om primærtests for N=h•2^n−1 // BIT Numerisk Matematik. - 1994. - T. 34 , no. 3 . - S. 451-454 . - doi : 10.1007/BF01935653 . Arkiveret fra originalen den 4. marts 2016.
Hans Riesel. Primtal og computermetoder til faktorisering. — 2. - Birkhäuser, 1994. - T. 126. - S. 107-121. — (Fremskridt i Matematik). — ISBN 0-8176-3743-5 .