Luc-Lehmer-Riesel teszt

A Lucas-Lehmer-Riesel teszt ( LLR ) a c alakú számok elsődlegességi tesztje (az ilyen számok egy részhalmazát Sabit számoknak nevezzük ). Hans Riesel által kifejlesztett és a Luc-Lehmer teszt alapján ez a leggyorsabb determinisztikus algoritmus az ilyen típusú számokra [1] . $N=k\cdot 2^{n}-1$ $2^{n}>k$ $3\cdot 2^{n}-1$

Algoritmus

Az algoritmus nagyon hasonlít a Luc-Lehmer teszthez, de olyan értékkel kezdődik, amely attól függ . Az algoritmushoz a Lucas sorozatot használjuk , amelyet a következő képlettel adunk meg: $k$ $\{u_{i}\}$ $i>0$

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

$N$ prím akkor és csak akkor, ha osztja . ${\displaystyle u_{n-2))$

Kezdőérték keresése

tok . Ha — páratlan, akkor a rendszer az értéket veszi fel . Ha , akkor veszik . Egyszerűen ezek Mersenne-számok . $k=1$ $n$ $u_{0}=4$ $n\equiv 3{\pmod {4}}$ $u_{0}=3$ $n$
tok . Az érték minden n ≡ 0,3 (mod 4) esetén használható. $k = 3$ $u_{0}=5778$ $n\equiv 0.3{\pmod {4}}$
Ha és nem osztható 3-mal, akkor az érték használható . $k\equiv 1.5{\pmod {6}}$ $N$ $u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}$
Más esetekben osztható 3-mal, és a helyes u 0 kezdőérték kiválasztása sokkal nehezebb. $k$

1994-ben megadtak egy alternatív módszert a kiindulási érték meghatározására [2] . A módszer sokkal egyszerűbb, mint amit Riesel használ arra az esetre, amikor 3 oszt . Az alternatív módszerben először keresse meg azt az értéket , amely kielégíti a következő Jacobi szimbólumegyenlőséget : $u_{0}$ $k$ $P$

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

és .

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

A gyakorlatban csak néhány értéket kell ellenőrizni (5, 8, 9 vagy 11 lefedi a 85%-ot). $P$

A kezdeti érték lekéréséhez használhatja a Lucas sorozatot [ 2] [3] . 3 ∤ k esetén (k nem osztható 3-mal) az érték használható, és nincs szükség előzetes keresésre. A kezdeti érték ekkor egyenlő a Lucas-szekvencia modulo értékével . Ez a folyamat nagyon kevés időt vesz igénybe a fő teszthez képest. $u_{0}$ $P$ ${\megjelenítési stílus (P,1)}$ $P=4$ $u_{0}$ $V_{k}(P,1)$ $N$

A vizsgálat mechanizmusa

A Luc-Lehmer-Riesel teszt egy speciális eset a csoport sorrendjének egyszerűségének ellenőrzésére. A teszt azt mutatja, hogy egy bizonyos szám prím, mivel egy bizonyos csoportnak van egy olyan sorrendje, amely megegyezik ezzel a prímszámmal, amelyhez a csoport egy elemét azonosítjuk, amelynek pontosan a kívánt sorrendje van.

A Luke-féle tesztekhez hasonló tesztek az egész számok másodfokú modulo kiterjesztésének szorzócsoportját használják egy számhoz . Ha prím, akkor a szorzócsoport sorrendje , és van egy rendű alcsoportja, a teszt céljaira ennek az alcsoportnak a generáló halmazát kell keresni. $N$ $N$ $N$ $N^{2}-1$ $N+1$

Találhat egy nem iteratív kifejezést a kifejezésre . A Lucas-Lehmer tesztmodellt követve indukcióval állítjuk be és kapjuk meg . $u_{i}$ $u_{i}=a^{{2^{i}}}+a^{{-2^{i}}}$ $u_{i}=u_{{i-1}}^{2}-2$

Tekintsük a sorozat 2 i -edik elemét . Ha a teljesít egy másodfokú egyenletet, akkor ez egy Lucas-sorozat, és engedelmeskedik a kifejezésnek . Valójában egy másik sorozat -edik elemét keressük, de mivel a Lucas-sorozat tizedelése (minden k -edik elem kiválasztása) egy Lucas-sorozatot is eredményez, a k faktort egy kiindulási pont kiválasztásával választhatjuk ki. $v(i)=a^{i}+a^{{-i}}$ $v(i)=\alpha v(i-1)+\beta v(i-2)$ $k\x 2^{i}$

LLR program

Az LLR egy olyan program, amely LLR tesztet hajt végre. A programot Jean Penné fejlesztette ki. Vincent Penné úgy módosította a programot, hogy ellenőrizni tudja egy szám elsődlegességét az interneten keresztül. A program egyéni keresésekhez is használható, de néhány elosztott számítástechnikai projektben is szerepel, mint például a Riesel Sieve és a PrimeGrid .

Lásd még

Riesel számok

Jegyzetek

↑ Az ezekhez hasonló Proth-számok elsődlegességének tesztelésére vagy a Proth - tételt ( valószínűségi algoritmus ), vagy a Brilhart, Lehmer és Selfridge által 1975-ben leírt determinisztikus algoritmusok valamelyikét használjuk – lásd Brillhart, Lehmer, Selfridge, 1975 $N=k\cdot 2^{n}+1$
↑ 1 2 Rodseth, 1994 .
↑ Riesel, 1994 , p. 194.

Irodalom

Hans Riesel. Lucasian Criteria for the Primal of N = h •2 n − 1 // A számítás matematikája. - 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 új elsődlegességi kritériumai és faktorizációi // Számítási matematika. - 1975. - 1. évf. 29. - Kiadás. 130 . - S. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
Öystein J. Rodseth. Megjegyzés az N=h•2^n−1 elsődlegességi tesztjéhez // BIT Numerical Mathematics. - 1994. - T. 34 , sz. 3 . - S. 451-454 . - doi : 10.1007/BF01935653 . Az eredetiből archiválva: 2016. március 4.
Hans Riesel. Prímszámok és számítógépes módszerek a faktorizáláshoz. — 2. - Birkhäuser, 1994. - T. 126. - S. 107-121. — (Előrehaladás a matematikában). — ISBN 0-8176-3743-5 .

Linkek

Töltse le Jean Penne LLR-jét
Math::Prime::Util::GMP – Perl modul, az LLR és Prot teszt alapvető megvalósítása, valamint néhány módszer Brilhart, Lemaire és Selfridge cikkéből.