Lucasův test primality - Lucas primality test
v výpočetní teorie čísel, Lucasův test je test primality pro přirozené číslo n; to vyžaduje, aby hlavní faktory z n - 1 již znám.[1][2] Je základem Pratt certifikát to dává výstižné ověření, že n je hlavní.
Koncepty
Nechat n být kladné celé číslo. Pokud existuje celé číslo A, 1 < A < n, takový, že
a pro každý hlavní faktor q z n − 1
pak n je hlavní. Pokud takové číslo neexistuje A tedy existuje n je buď 1, 2, nebo kompozitní.
Důvod správnosti tohoto tvrzení je následující: platí-li první rovnocennost A, to můžeme odvodit A a n jsou coprime. Li A přežije také druhý krok, poté objednat z A v skupina (Z/nZ)* je rovný n−1, což znamená, že pořadí této skupiny je n−1 (protože pořadí každého prvku skupiny rozděluje pořadí skupiny), z čehož vyplývá, že n je primární. Naopak, pokud n je hlavní, pak existuje a primitivní root modulo n nebo generátor skupiny (Z/nZ) *. Takový generátor má řád | (Z/nZ)*| = n−1 a obě ekvivalence budou platit pro každý takový primitivní kořen.
Všimněte si, že pokud existuje A < n tak, že první ekvivalence selže, A se nazývá a Fermatův svědek pro úplnost n.
Příklad
Například vezměte n = 71. Pak n - 1 = 70 a hlavní faktory 70 jsou 2, 5 a 7. Náhodně vybereme a = 17 < n. Nyní vypočítáme:
Pro všechna celá čísla A je známo že
Proto multiplikativní pořadí 17 (mod 71) není nutně 70, protože výše uvedený faktor 70 může také fungovat. Zkontrolujte tedy 70 děleno jeho hlavními faktory:
Bohužel máme 1710≡1 (mod 71). Stále tedy nevíme, jestli je 71 prvočíslo nebo ne.
Zkusíme další náhodný A, tentokrát výběr A = 11. Nyní vypočítáme:
To opět neukazuje, že multiplikativní pořadí 11 (mod 71) je 70, protože může také fungovat nějaký faktor 70. Zkontrolujte tedy 70 děleno jeho hlavními faktory:
Takže multiplikativní řád 11 (mod 71) je 70, a tedy 71 je prvočíslo.
(Provést je modulární umocňování, jeden by mohl použít rychlý algoritmus umocňování jako binární nebo umocňování přídavného řetězce ).
Algoritmus
Algoritmus lze zapsat pseudo kód jak následuje:
algoritmus lucas_primality_test je vstup: n > 2, liché celé číslo, které má být testováno na primitivitu. k, parametr, který určuje přesnost testu. výstup: primární -li n je prime, jinak kompozitní nebo případně složený. určit hlavní faktory n-1. LOOP1: opakovat k časy: vybrat A náhodně v rozsahu [2, n − 1] -li pak vrátit se kompozitní jiný # LOOP2: pro všechny hlavní faktory q z n−1: -li pak -li zkontrolovali jsme tuto rovnost pro všechny hlavní faktory n−1 pak vrátit se primární jiný pokračovat LOOP2 jiný # pokračovat LOOP1 vrátit se možná složený.
Viz také
- Édouard Lucas, pro něž je tento test pojmenován
- Fermatova malá věta
- Pocklingtonův test primality, vylepšená verze tohoto testu, která vyžaduje pouze částečnou faktorizaci n − 1
- Osvědčení o prvenství
Poznámky
- ^ Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: A Computational Perspective (2. vydání). Springer. str. 173. ISBN 0-387-25282-7.
- ^ Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 přednášek o číslech Fermat: od teorie čísel po geometrii. CMS knihy z matematiky. 9. Kanadská matematická společnost / Springer. str. 41. ISBN 0-387-95332-9.