Luc-Lehmer-Riesel testi

Lucas-Lehmer-Riesel-testi ( LLR ) on primaliteettitesti muotoa c oleville numeroille (tällaisten lukujen osajoukkoa kutsutaan sabit-luvuiksi ). Hans Rieselin kehittämä ja Luc -Lehmerin testiin perustuva se on nopein deterministinen algoritmi tällaisille luvuille [1] . $N=k\cdot 2^{n}-1$ $2^{n}>k$ $3\cdot 2^{n}-1$

Algoritmi

Algoritmi on hyvin samanlainen kuin Luc-Lehmer-testi, mutta alkaa arvolla, joka riippuu . Algoritmissa käytetään Lucas-sekvenssiä , joka saadaan kaavalla: $k$ $\{u_{i}\}$ $i>0$

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

$N$ on alkuluku jos ja vain jos se jakaa . ${\displaystyle u_{n-2))$

Alkuarvon etsiminen

tapaus . Jos — on pariton, arvoksi otetaan . Jos , niin on otettu . Yksinkertaisesti nämä ovat Mersennen numeroita . $k = 1$ $n$ $u_{0}=4$ $n\equiv 3{\pmod {4}}$ $u_{0}=3$ $n$
tapaus . Arvoa voidaan käyttää kaikille n ≡ 0,3 (mod 4). $k = 3$ $u_{0}=5778$ $n\equiv 0.3{\pmod {4}}$
Jos ja ei ole jaollinen 3:lla, arvoa voidaan käyttää . $k\equiv 1.5{\pmod {6}}$ $N$ $u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}$
Muissa tapauksissa se on jaollinen kolmella, ja oikean aloitusarvon u 0 valitseminen on paljon vaikeampaa. $k$

Vaihtoehtoinen menetelmä lähtöarvon löytämiseksi esitettiin vuonna 1994 [2] . Menetelmä on paljon yksinkertaisempi kuin Rieselin käyttämä tapaus, jossa 3 jakaa . Etsi vaihtoehtoisessa menetelmässä ensin arvo , joka täyttää seuraavan Jacobin symboliyhtälön : $u_{0}$ $k$ $P$

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

ja .

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

Käytännössä vain muutama arvo on tarkistettava (5, 8, 9 tai 11 kattavat 85 %). $P$

Alkuarvon saamiseksi voit käyttää Lucas-sekvenssiä [2] [3] . Arvolle 3 ∤ k (k ei ole jaollinen 3:lla) arvoa voidaan käyttää, eikä esihakua tarvita. Alkuarvo on tällöin yhtä suuri kuin Lucas-sekvenssi modulo . Tämä prosessi vie hyvin vähän aikaa verrattuna päätestiin. $u_{0}$ $P$ ${\näyttötyyli (P,1)}$ $P=4$ $u_{0}$ $V_{k}(P,1)$ $N$

Testin mekanismi

Luc-Lehmer-Riesel-testi on erityinen tapaus tarkistaa ryhmän järjestyksen yksinkertaisuus. Testi osoittaa, että tietty luku on alkuluku, koska tietyllä ryhmällä on järjestys, joka olisi yhtä suuri kuin tämä alkuluku, jolle tunnistetaan ryhmän elementti, jolla on täsmälleen haluttu järjestys.

Testit, kuten Luken testit, käyttävät kokonaislukujen neliöllisen modulolaajennuksen kertovaa ryhmää luvulle . Jos on alkuluku, kertovan ryhmän järjestys on , ja sillä on järjestyksen aliryhmä, testiä varten etsitään tämän aliryhmän generoiva joukko . $N$ $N$ $N$ $N^{2}-1$ $N+1$

Löydät ei-iteratiivisen lausekkeen sanalle . Lucas-Lehmerin testimallia noudattaen asetetaan ja saadaan induktiolla . $u_{i}$ $u_{i}=a^{{2^{i}}}+a^{{-2^{i}}}$ $u_{i}=u_{{i-1}}^{2}-2$

Tarkastellaan sekvenssin 2 i -osaa . Jos a täyttää toisen asteen yhtälön, se on Lucas-sekvenssi ja noudattaa lauseketta . Itse asiassa etsimme toisen sekvenssin -:nnettä elementtiä, mutta koska Lucas-sekvenssin desimointi (valitsemalla jokainen k -osa alkio) tuottaa myös Lucas-sekvenssin, voimme valita tekijän k valitsemalla aloituspisteen. $v(i)=a^{i}+a^{{-i}}$ $v(i)=\alpha v(i-1)+\beta v(i-2)$ $k\kertaa 2^{i}$

LLR-ohjelma

LLR on ohjelma, joka suorittaa LLR-testin. Ohjelman on kehittänyt Jean Penné. Vincent Penné muokkasi ohjelmaa niin, että voit tarkistaa luvun ensisijaisuuden Internetin kautta. Ohjelmaa voidaan käyttää sekä yksittäisiin hakuihin, mutta se sisältyy myös joihinkin hajautettuihin laskentaprojekteihin , kuten Riesel Sieve ja PrimeGrid .

Katso myös

Riesel numerot

Muistiinpanot

↑ Näitä vastaavien Proth - lukujen primaalisuuden testaamiseen käytetään joko Proth - lausetta ( todennäköisyyspohjainen algoritmi ) tai jotakin Brilhartin, Lehmerin ja Selfridgen vuonna 1975 kuvaamista deterministisista algoritmeista - katso Brillhart, Lehmer, Selfridge, 1975 $N=k\cdot 2^{n}+1$
↑ 1 2 Rodseth, 1994 .
↑ Riesel, 1994 , s. 194.

Kirjallisuus

Hans Riesel. Lucasian kriteerit primaalisuuden N = h •2 n − 1 // Mathematics of Computation. - American Mathematical Society, 1969. - V. 23 , no. 108 . - S. 869-875 . - doi : 10.2307/2004975 . — .
John Brillhart, Derrick Henry Lehmer, John Selfridge. 2^m ± 1:n uudet primaalisuuskriteerit ja faktorisaatiot // Laskennan matematiikka. - 1975. - Voi. 29. - Ongelma. 130 . - S. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
Öystein J. Rodseth. Huomautus primailiteettitesteistä N=h•2^n−1 // BIT Numerical Mathematics. - 1994. - T. 34 , no. 3 . - S. 451-454 . - doi : 10.1007/BF01935653 . Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
Hans Riesel. Alkuluvut ja tietokonemenetelmät faktorointiin. – 2. - Birkhäuser, 1994. - T. 126. - S. 107-121. — (Matematiikan edistyminen). — ISBN 0-8176-3743-5 .

Linkit

Lataa Jean Pennen LLR
Math::Prime::Util::GMP — Perl-moduuli, LLR- ja Prot-testin perustoteutus ja joitain menetelmiä Brilhartin, Lemairen ja Selfridgen artikkelista.