Test primality - Primality test

A test primality je algoritmus pro určení, zda je vstupní číslo primární. Mezi další oblasti matematika, používá se pro kryptografie. Na rozdíl od celočíselná faktorizace, testy primality obecně nedávají hlavní faktory, pouze s uvedením, zda je vstupní číslo prvočíslo nebo ne. Faktorizace je považována za výpočetně obtížný problém, zatímco testování primality je poměrně snadné (jeho provozní doba je polynomiální ve velikosti vstupu). Některé testy primality dokázat že číslo je prvočíslo, zatímco ostatní mají rádi Miller – Rabin dokázat, že číslo je kompozitní. Ten druhý by proto mohl být přesněji nazýván zkoušky složitosti místo testů primality.

Jednoduché metody

Nejjednodušší test primality je zkušební rozdělení: zadáno vstupní číslo, n, zkontrolujte, zda je rovnoměrné dělitelný kterýmkoli prvočíslo mezi 2 a √n (tj. že rozdělení nezanechává č zbytek ). Pokud ano, pak n je kompozitní. Jinak je primární.^[1]

Zvažte například číslo 100, které je rovnoměrně dělitelné těmito čísly:

2, 4, 5, 10, 20, 25, 50

Všimněte si, že největší faktor, 50, je polovina ze 100. To platí pro všechny n: všichni dělitelé jsou menší nebo rovni n / 2.

Vlastně, když testujeme všechny možné dělitele až n / 2, objevíme některé faktory dvakrát. Chcete-li to dodržet, přepište seznam dělitelů jako seznam produktů, každý se rovná 100:

2 × 50,   4 × 25,   5 × 20,   10 × 10,   20 × 5,   25 × 4,   50 × 2

Všimněte si, že produkty minuly 10 x 10 pouze opakujte čísla, která se objevila v dřívějších produktech. Například, 5 x 20 a 20 x 5 se skládají ze stejných čísel. To platí pro všechny n: všichni jedineční dělitelé n jsou čísla menší nebo rovna √n, takže to nemusíme prohledávat.^[1] (V tomto příkladu √n = √100 = 10.)

Všechna sudá čísla větší než 2 lze také vyloučit, protože pokud se sudé číslo může rozdělit n, tak může 2.

Pojďme pomocí zkušebního dělení otestovat primitivitu 17. Potřebujeme pouze test dělitelů do √n, tj. celá čísla menší nebo rovna ${ displaystyle scriptstyle { sqrt {17}} přibližně 4,12}$, jmenovitě 2, 3 a 4. Můžeme přeskočit 4, protože je to sudé číslo: pokud by 4 dokázalo rovnoměrně rozdělit 17, 2 by také, a 2 je již v seznamu. Zbývá 2 a 3. Dělíme 17 každým z těchto čísel a zjistíme, že ani jeden nedělí 17 rovnoměrně - obě divize zanechávají zbytek. 17 je tedy prime.

Tuto metodu můžeme dále vylepšit. Všimněte si, že všechna prvočísla větší než 3 jsou ve formě 6k ± 1, kde k je celé číslo větší než 0. Je to proto, že všechna celá čísla lze vyjádřit jako (6k + i), kde i = −1, 0, 1, 2, 3 nebo 4. Všimněte si, že 2 rozdělují (6k + 0), (6k + 2) a (6k + 4) a 3 příčky (6k + 3). Účinnější metodou je tedy otestovat, zda n je dělitelné 2 nebo 3, poté zkontroluje všechna čísla formuláře ${ displaystyle scriptstyle 6k pm 1 leq { sqrt {n}}}$. To je třikrát rychlejší než testování všech čísel √n.

Dále generalizovat, všechna prvočísla větší než C# (c první ) jsou ve formě C# · k + i, pro i < C#, kde C a k jsou celá čísla a i představuje čísla, která jsou coprime na C#. Například nechte C = 6. Pak C# = 2 · 3 · 5  = 30. Všechna celá čísla jsou ve tvaru 30k + i pro i = 0, 1, 2,...,29 a k celé číslo. 2 však dělí 0, 2, 4, ..., 28; 3 dělí 0, 3, 6, ..., 27; a 5 dělí 0, 5, 10, ..., 25. Takže všechna prvočísla větší než 30 mají tvar 30k + i pro i = 1, 7, 11, 13, 17, 19, 23, 29 (tj. pro i < 30 takhle gcd (i,30) = 1). Všimněte si, že pokud i a 30 tedy nebylo coprime 30k + i by byl dělitelný prvočíselným dělitelem 30, jmenovitě 2, 3 nebo 5, a nebyl by tedy prvočíselný. (Poznámka: Ne všechna čísla, která splňují výše uvedené podmínky, jsou prvočísla. Například: 437 je ve tvaru c # k + i pro c # (7) = 210, k = 2, i = 17. 437 je však složený číslo rovnající se 19 * 23).

Tak jako C → ∞, počet hodnot, které C#k + i může převzít určitý rozsah se snižuje, a tak čas na testování n klesá. U této metody je také nutné zkontrolovat dělitelnost všemi prvočísly, která jsou menší než C. Lze použít pozorování analogická s předchozím rekurzivně, dávat Síto Eratosthenes.

Dobrým způsobem, jak tyto metody (a všechny ostatní uvedené níže) urychlit, je předpočítat a uložit seznam všech prvočísel do určité hranice, řekněme všech prvočísel do 200. (Takový seznam lze vypočítat pomocí Síto Eratosthenes nebo algoritmem, který testuje každou přírůstkovou hodnotu m proti všem známým prvočíslům < √m). Pak před testováním n za primitivnost seriózní metodou, n nejdříve lze zkontrolovat dělitelnost libovolným prvočíslem ze seznamu. Pokud je dělitelné kterýmkoli z těchto čísel, je složené a jakékoli další testy lze přeskočit.

Používá jednoduchý, ale velmi neúčinný test primality Wilsonova věta, který uvádí, že str je hlavní, právě když:

${ displaystyle (p-1)! equiv -1 { pmod {p}} ,}$

Ačkoli tato metoda vyžaduje asi str modulární multiplikace, což je nepraktické, věty o prvočíslech a modulárních zbytcích tvoří základ mnoha praktičtějších metod.

Pythonský kód

Následuje jednoduchý test primality v Pythonský kód pomocí jednoduchého 6k ± 1 optimalizace zmíněná dříve. Složitější metody popsané níže jsou u velkých mnohem rychlejší n.

def is_prime(n: int) -> bool:    "" "Test primality využívající optimalizaci 6k + -1." ""    -li n <= 3:        vrátit se n > 1    -li n % 2 == 0 nebo n % 3 == 0:        vrátit se Nepravdivé    i = 5    zatímco i ** 2 <= n:        -li n % i == 0 nebo n % (i + 2) == 0:            vrátit se Nepravdivé        i += 6    vrátit se Skutečný

Heuristické testy

Jedná se o testy, které se zdají v praxi dobře fungovat, ale nejsou prokázané, a proto z technického hlediska nejde o algoritmy. Fermatův test a Fibonacciho test jsou jednoduchými příklady a jsou velmi efektivní při kombinaci. John Selfridge se domníval, že pokud str je liché číslo a str ≡ ± 2 (mod 5), pak str bude primární, pokud platí obě z následujících možností:

• 2^str−1 ≡ 1 (mod str),
• F_str+1 ≡ 0 (mod str),

kde F_k je k-th Fibonacciho číslo. První podmínkou je Fermatův test primality pomocí základny 2.

Obecně, pokud str ≡ a (mod X²+4), kde A je kvadratický zbytek (mod X²+4) poté str by měla být primární, pokud platí následující podmínky:

• 2^str−1 ≡ 1 (mod str),
• F(X)_str+1 ≡ 0 (mod str),

F(X)_k je k-th Fibonacciho polynom na X.

Selfridge, Carl Pomerance, a Samuel Wagstaff společně nabízejí 620 $ za protiklad. Problém je stále otevřený od 11. září 2015.^[2]

Pravděpodobnostní testy

Pravděpodobnostní testy jsou přísnější než heuristika v tom, že poskytují prokazatelné hranice pravděpodobnosti, že budou oklamáni složeným číslem. Mnoho populárních testů primality jsou testy pravděpodobnostní. Tyto testy používají, kromě testovaného počtu n, některá další čísla A které jsou z některých vybrány náhodně ukázkový prostor; obvyklé randomizované testy primality nikdy nehlásí prvočíslo jako složené, ale je možné, aby složené číslo bylo hlášeno jako prvočíslo. Pravděpodobnost chyby lze snížit opakováním testu s několika nezávisle zvolenými hodnotami A; pro dva běžně používané testy, pro žádný kompozitní n alespoň polovina A'detekovat n's kompozičnost, tak k opakování snižují pravděpodobnost chyby na maximálně 2^−k, kterou lze zvětšit libovolně malou k.

Základní struktura randomizovaných testů primality je následující:

1. Náhodně vyberte číslo A.
2. Zkontrolujte určitou rovnost (odpovídající zvolenému testu) zahrnující A a dané číslo n. Pokud rovnost neplatí, pak n je složené číslo, A je znám jako svědek pro úplnost a test se zastaví.
3. Opakujte od kroku 1, dokud nedosáhnete požadované přesnosti.

Po jedné nebo více iteracích, pokud n není shledáno jako složené číslo, pak jej lze deklarovat pravděpodobně prime.

Fermatův test primality

Nejjednodušší pravděpodobnostní test primality je Fermatův test primality (ve skutečnosti test složení). Funguje to následovně:

Dáno celé číslo n, vyberte celé číslo A coprime na n a vypočítat A^{n − 1} modulo n. Pokud se výsledek liší od 1, pak n je složený. Pokud je to 1, pak n může být prime.

Li Aⁿ⁻¹ (modulo n) je 1 ale n tedy není prime n se nazývá apseudoprime na základnu A. V praxi to pozorujeme, pokudAⁿ⁻¹ (modulo n) je tedy 1 n je obvykle prime. Zde je ale příklad: pokud n = 341 a A = 2, tedy

${ displaystyle 2 ^ {340} equiv 1 { pmod {341}}}$

i když je 341 = 11,31 složený. Ve skutečnosti je 341 nejmenší pseudoprime základna 2 (viz obrázek 1 z^[3]).

Existuje pouze 21853 pseudoprimesů báze 2, které jsou menší než 2,5×10¹⁰ (viz strana 1005 ze dne ^[3]). To znamená, že pro n až 2,5×10¹⁰, pokud 2ⁿ⁻¹ (modulo n) se tedy rovná 1 n je hlavní, pokud n je jedním z těchto 21853 pseudoprimesů.

Některá složená čísla (Carmichael čísla ) mají vlastnost, která A^{n − 1} je 1 (modulo n) pro každého A to je coprime n. Nejmenší příklad je n = 561 = 3,11,17, za což A⁵⁶⁰ je 1 (modulo 561) pro všechny A coprime na 561. Nicméně, Fermatův test se často používá, pokud je nutný rychlý screening čísel, například ve fázi klíčové generace Kryptografický algoritmus veřejného klíče RSA.

Miller – Rabin a Solovay – Strassen test primality

The Miller – Rabinův test primality a Test primality Solovay – Strassen jsou sofistikovanější varianty, které detekují všechny kompozity (opět to znamená: pro každý složené číslo n, alespoň 3/4 (Miller – Rabin) nebo 1/2 (Solovay – Strassen) čísel A jsou svědky složitosti n). Jedná se také o testy složení.

Test primality podle Millera a Rabina funguje následovně: Je dáno celé číslo n, vyberte nějaké kladné celé číslo A < n. Nechť 2^sd = n - 1, kde d je zvláštní. Li

${ displaystyle a ^ {d} ne ekviv 1 { pmod {n}}}$

a

${ displaystyle a ^ {2 ^ {r} d} ne ekv. -1 { pmod {n}}}$ pro všechny ${ displaystyle 0 leq r leq s-1,}$

pak n je složený a A je svědkem složitosti. V opačném případě, n může nebo nemusí být prime. Miller-Rabinův test je a silný pseudoprime test (viz PSW^[3] strana 1004).

Test Solovay – Strassenovy primality používá jinou rovnost: dostalo liché číslo n, vyberte celé číslo A < n, pokud

${ displaystyle a ^ {(n-1) / 2} not equiv left ({ frac {a} {n}} right) { pmod {n}}}$, kde ${ displaystyle left ({ frac {a} {n}} right)}$ je Jacobi symbol,

pak n je složený a A je svědkem složitosti. V opačném případě, n může nebo nemusí být prime. Test Solovay – Strassen je Eulerův pseudoprime test (viz PSW^[3] strana 1003).

Pro každou jednotlivou hodnotu Aje test Solovay – Strassen slabší než test Miller – Rabin. Například pokud n = 1905 a A = 2, pak to ukazuje Miller-Rabinův test n je složený, ale Solovay – Strassenův test nikoli. Je to proto, že 1905 je Eulerpseudoprime base 2, ale ne silná pseudoprime base 2 (je to znázorněno na obrázku 1 PSW^[3]).

Frobeniův test primality

Testy primality Miller – Rabin a Solovay – Strassen jsou jednoduché a jsou mnohem rychlejší než jiné obecné testy primality. Jednou z metod dalšího zvyšování účinnosti v některých případech je Frobeniův test pseudoprimality; kolo tohoto testu trvá asi třikrát déle než kolo Miller – Rabin, ale dosahuje pravděpodobnostní hranice srovnatelné se sedmi koly Miller – Rabin.

Test Frobenius je zevšeobecněním Lucas pseudoprime test.

Baityho-PSW test primality

The Baillie – PSW test primality je pravděpodobnostní test primality, který kombinuje Fermatův nebo Miller-Rabinův test s a Lucas pravděpodobně prime test pro získání testu primality, který nemá žádné známé protiklady. To znamená, že neexistují žádné známé kompozity n pro které tento test uvádí, že n je pravděpodobně hlavní.^[4] Ukázalo se, že neexistují žádné protiklady pro n ${ displaystyle <2 ^ {64}}$.

Další testy

Leonard Adleman a Ming-Deh Huang představili bezchybnou (ale očekávanou polynomiálně) variantu test prvočíselnosti eliptické křivky. Na rozdíl od ostatních pravděpodobnostních testů tento algoritmus vytváří a osvědčení o prvenství, a lze jej tedy použít k prokázání, že číslo je prvočíslo.^[5] Algoritmus je v praxi neúměrně pomalý.

Li kvantové počítače byly k dispozici, bylo možné otestovat primitivitu asymptoticky rychlejší než pomocí klasických počítačů. Kombinace Shorův algoritmus, metoda celočíselné faktorizace s Pocklingtonův test primality mohl vyřešit problém v ${ displaystyle O (( log n) ^ {3} ( log log n) ^ {2} log log log n)}$.^[6]

Rychlé deterministické testy

Blízko počátku 20. století se ukázalo, že důsledkem je Fermatova malá věta lze použít k testování primality.^[7] To mělo za následek Pocklingtonův test primality.^[8] Protože však tento test vyžaduje částečný faktorizace z n - 1 doba běhu byla v nejhorším případě stále poměrně pomalá. První deterministický test primality výrazně rychlejší než naivní metody test cyklotomie; lze prokázat jeho běhovou dobu Ó ((logn)^{C log log logn}), kde n je číslo pro testování primality a C je konstanta nezávislá na n. Bylo provedeno mnoho dalších vylepšení, ale u žádného nemohlo být prokázáno, že má polynomiální dobu běhu. (Upozorňujeme, že doba běhu se měří z hlediska velikosti vstupu, který je v tomto případě ~ logn, což je počet bitů potřebných k vyjádření počtu n.) test prvočíselnosti eliptické křivky lze prokázat, že běží v O ((logn)⁶), pokud nějaké dohady analytická teorie čísel jsou pravdivé.^{[který? ]} Podobně pod zobecněná Riemannova hypotéza, deterministický Millerův test, který tvoří základ pravděpodobnostního Miller-Rabinova testu, lze prokázat, že do něj vstupuje Ó ((logn)⁴).^[9] V praxi je tento algoritmus pomalejší než ostatní dva, pokud jde o velikosti čísel, s nimiž lze vůbec pracovat. Protože implementace těchto dvou metod je poměrně obtížná a vytváří riziko programovacích chyb, jsou často preferovány pomalejší, ale jednodušší testy.

V roce 2002 vynalezl první prokazatelně bezpodmínečný deterministický polynomiální časový test primality Manindra Agrawal, Neeraj Kayal, a Nitin Saxena. The Test prvosti AKS běží v Õ ((logn)¹²) (vylepšeno na Õ ((logn)^7.5)^[10] ve zveřejněné revizi jejich příspěvku), kterou lze dále snížit na Õ ((logn)⁶) pokud Domněnka Sophie Germainové je pravda.^[11] Následně Lenstra a Pomerance představili verzi testu, která běží v čase Õ ((logn)⁶) bezpodmínečně.^[12]

Agrawal, Kayal a Saxena navrhují variantu svého algoritmu, který by běžel v Õ ((logn)³) pokud Agrawalova domněnka je pravda; heuristický argument Hendrika Lenstry a Carla Pomerance však naznačuje, že je pravděpodobně nepravdivý.^[10] Upravená verze domněnky Agrawal, domněnka Agrawal – Popovych,^[13] může být stále pravda.

Složitost

v teorie výpočetní složitosti, formální jazyk odpovídající prvočíslům se označuje jako PRIMES. Je snadné ukázat, že PRIMES je uvnitř Co-NP: jeho doplněk KOMPOZITY je v NP protože lze určit kompozičnost nedeterministickým odhadem faktoru.

V roce 1975 Vaughan Pratt ukázal, že existuje certifikát primality, který byl zkontrolovatelný v polynomiálním čase, a tedy že PRIMES byl v NP, a tedy v NP ∩ coNP. Vidět osvědčení o prvenství pro detaily.

Následný objev algoritmů Solovay – Strassen a Miller – Rabin dal PRIMES coRP. V roce 1992 byl použit algoritmus Adleman – Huang^[5] snížil složitost na ZPP = RP ∩ coRP, který nahradil Prattův výsledek.

The Adleman – Pomerance – Rumely test primality od roku 1983 vložte PRIMES QP (kvazi-polynomiální čas ), o kterém není známo, že by byl srovnatelný s výše uvedenými třídami.

Vzhledem k jeho použitelnosti v praxi, algoritmům polynomiálního času za předpokladu Riemannovy hypotézy a dalším podobným důkazům bylo dlouho podezření, ale neprokázalo se, že by primalita mohla být vyřešena v polynomiálním čase. Existence Test prvosti AKS nakonec vyřešil tuto dlouholetou otázku a umístil PRIMES dovnitř P. Není však známo, že by byl PRIMES P-kompletní, a není známo, zda to spočívá ve třídách ležících uvnitř P jako NC nebo L. Je známo, že PRIMES není v AC⁰.^[14]

Metody číselné teorie

Existují určité metody číselné teorie pro testování, zda je číslo prvočíslo, například Lucasův test a Prothův test. Tyto testy obvykle vyžadují faktorizaci n + 1, n - 1 nebo podobná veličina, což znamená, že nejsou užitečné pro testování primality pro všeobecné účely, ale jsou často docela silné, když je testovaný počet n je známo, že má zvláštní formu.

Lucasův test se opírá o skutečnost, že multiplikativní pořadí čísla A modulo n je n - 1 pro prvočíslo n když A je primitivní kořenový modul č. Pokud můžeme ukázat A je primitivní pro n, můžeme ukázat n je hlavní.

Reference

Zdroje

externí odkazy

• Excel vzorec (ExcelExchange.com)
• Solovay-Strassen (computacion.cs.cinvestav.mx) na Archiv. Dnes (archivováno 2012-12-20) - Implementace testu primality Solovay-Strassen v Maple
• Rozlišování prvočísel od složených čísel, D.J. Bernstein (cr.yp.to)
• Hlavní stránky (primes.utm.edu)
• Lucasův test primality s faktorem N - 1 (MathPages.com) na Knihovna Kongresu Webové archivy (archivovány 6. 8. 2010)
• PRIMABOINCA je výzkumný projekt, který pomocí počítačů připojených k internetu vyhledává a protiklad k nějakým dohadům. První domněnka (Agrawalova domněnka ) byl základem pro formulaci prvního deterministického algoritmu prime test v polynomiálním čase (Algoritmus AKS ).