Luc-Lehmer-Rieselův test

Lucas-Lehmer-Riesel test ( LLR ) je test primality pro čísla ve tvaru c (podmnožina takových čísel se nazývá čísla Sabit ). Vyvinutý Hansem Rieselem a založený na Luc-Lehmerově testu je nejrychlejším deterministickým algoritmem pro čísla tohoto druhu [1] . $N=k\cdot 2^{n}-1$ $2^{n}>k$ $3\cdot 2^{n}-1$

Algoritmus

Algoritmus je velmi podobný Luc-Lehmer testu, ale začíná hodnotou, která závisí na . Pro algoritmus se používá Lucasova sekvence , která je dána vzorcem: $k$ $\{u_{i}\}$ $i>0$

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

$N$ je prvočíslo právě tehdy, když dělí . ${\displaystyle u_{n-2))$

Nalezení počáteční hodnoty

případ . Pokud je — liché, pak se bere hodnota . Pokud , pak se bere . Pro zjednodušení jsou to Mersennova čísla . $k=1$ $n$ $u_{0}=4$ $n\equiv 3{\pmod {4}}$ $u_{0}=3$ $n$
případ . Hodnotu lze použít pro všechna n ≡ 0,3 (mod 4). $k = 3$ $u_{0}=5778$ $n\equiv 0.3{\pmod {4}}$
Pokud a není dělitelné 3, lze použít hodnotu . $k\equiv 1.5{\pmod {6}}$ $N$ $u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}$
V ostatních případech je dělitelná 3 a výběr správné počáteční hodnoty u 0 je mnohem obtížnější. $k$

Alternativní metoda pro zjištění výchozí hodnoty byla uvedena v roce 1994 [2] . Metoda je mnohem jednodušší než metoda používaná Rieselem pro případ, kdy se dělí 3 . V alternativní metodě nejprve najděte hodnotu , která vyhovuje následující rovnosti Jacobiho symbolu : $u_{0}$ $k$ $P$

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

a .

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

V praxi je třeba zkontrolovat pouze několik hodnot (5, 8, 9 nebo 11 pokrývá 85 %). $P$

Pro získání počáteční hodnoty můžete použít Lucasovu sekvenci [2] [3] . Pro 3 ∤ k (k není dělitelné 3) lze hodnotu použít a není potřeba žádné předběžné vyhledávání. Počáteční hodnota je pak rovna Lucasově sekvenci modulo . Tento proces trvá velmi málo času ve srovnání s hlavním testem. $u_{0}$ $P$ $(P,1)$ $P=4$ $u_{0}$ $V_{k}(P,1)$ $N$

Mechanismus testu

Luc-Lehmer-Rieselův test je speciální případ kontroly jednoduchosti uspořádání skupiny. Test ukazuje, že určité číslo je prvočíslo díky tomu, že určitá skupina má pořadí, které by se rovnalo tomuto prvočíslu, pro které je identifikován prvek skupiny, který má přesně požadované pořadí.

Testy jako Lukovy testy používají multiplikativní grupu kvadratického modulového rozšíření celých čísel pro číslo . Jestliže je prvočíslo, pořadí multiplikativní grupy je , a má podskupinu řádu , pro účely testu se hledá generující množina této podskupiny. $N$ $N$ $N$ $N^{2}-1$ $N+1$

Můžete najít neiterativní výraz pro . Podle Lucas-Lehmerova testovacího modelu nastavíme a získáme indukcí . $u_{i}$ $u_{i}=a^{{2^{i}}}+a^{{-2^{i}}}$ $u_{i}=u_{{i-1}}^{2}-2$

Uvažujme 2 i -tý prvek posloupnosti . Pokud a splňuje kvadratickou rovnici, je to Lucasova posloupnost a řídí se výrazem . Ve skutečnosti hledáme -tý prvek jiné posloupnosti, ale protože decimováním (výběrem každého k -tého prvku) Lucasovy posloupnosti také vznikne Lucasova posloupnost, můžeme zvolit faktor k výběrem počátečního bodu. $v(i)=a^{i}+a^{{-i}}$ $v(i)=\alpha v(i-1)+\beta v(i-2)$ $k\krát 2^{i}$

Program LLR

LLR je program, který provádí test LLR. Program vyvinul Jean Penné. Vincent Penné upravil program tak, abyste si mohli ověřit prvočíslo čísla přes internet. Program lze použít jak pro individuální vyhledávání, ale je také součástí některých distribuovaných výpočetních projektů včetně Riesel Sieve a PrimeGrid .

Viz také

Riesel čísla

Poznámky

↑ K testování primality Prothových čísel podobných těmto - se používá buď Prothova věta ( pravděpodobnostní algoritmus ) nebo některý z deterministických algoritmů popsaných Brilhartem, Lehmerem a Selfridgem v roce 1975 - viz Brillhart, Lehmer, Selfridge, 1975 $N=k\cdot 2^{n}+1$
↑ 1 2 Rodseth, 1994 .
↑ Riesel, 1994 , s. 194.

Literatura

Hans Riesel. Lucasiánská kritéria pro primálnost N = h •2 n − 1 // Matematika počítání. - American Mathematical Society, 1969. - V. 23 , no. 108 . - S. 869-875 . - doi : 10.2307/2004975 . — .
John Brillhart, Derrick Henry Lehmer, John Selfridge. Nová kritéria primality a faktorizace 2^m ± 1 // Matematika počítání. - 1975. - Sv. 29. - Vydání. 130 . - S. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
Öystein J. Rodseth. Poznámka k primárním testům pro N=h•2^n−1 // BIT Numerická matematika. - 1994. - T. 34 , no. 3 . - S. 451-454 . - doi : 10.1007/BF01935653 . Archivováno z originálu 4. března 2016.
Hans Riesel. Prvočísla a počítačové metody faktorizace. — 2. - Birkhäuser, 1994. - T. 126. - S. 107-121. — (Pokrok v matematice). — ISBN 0-8176-3743-5 .

Odkazy

Stáhněte si Jean Penne's LLR
Math::Prime::Util::GMP — Perl modul, základní implementace LLR a Prot testu a některé metody z článku Brilhart, Lemaire a Selfridge.