Test primality

Test primality je algoritmus zjistit, v případě, že číslo je prvočíslo .

Naivní metoda

Nejjednodušší test je následující: k testování N zkontrolujeme, zda je dělitelný jedním z celých čísel obsažených v širším smyslu mezi 2 a N-1. Pokud je odpověď záporná, pak N je prvočíslo, jinak je složená.

Výkon tohoto algoritmu zlepšuje několik změn:

Pravděpodobnostní testy

Pravděpodobnostní testy nejsou testy primality v užším slova smyslu (jsou součástí metod Monte-Carlo ): neumožňují s jistotou zaručit, že číslo je prvočíslo, ale jejich nízké náklady na výpočetní čas z nich činí vynikající kandidáty na aplikace v kryptologii často kriticky závisí na velkých prvočíslech a akceptují chybovost za předpokladu, že je velmi nízká: nazývají se průmyslovými prvočísly  (in) . Základní myšlenka testování primality čísla N je následující:

  1. Náhodně nakreslete číslo a .
  2. Zkontrolujte, zda určitou identitu , která zahrnuje si jako i vzhledem k tomu, číslo N a která je true, pokud je číslo N je připravit. Pokud není identita uspokojena, pak N je nutně složená a test se zastaví; v tomto případě se a nazývá zkušební svědek .
  3. Opakujte krok 1, dokud není dosaženo požadované hranice nejistoty.

Po několika iteracích, pokud N není rozpoznáno jako složené číslo , je prohlášeno za pravděpodobně prvočíslo .

Po provedení testu mohou existovat určitá složená čísla, která jsou bez ohledu na svědka prohlášena za „pravděpodobně prvotřídní“. Taková čísla odolná vůči testu se pro tento test nazývají čísla pseudoprime .

Nejjednodušším pravděpodobnostním testem primality je Fermatův test primality . Miller-Rabin primality zkouška a zkouška primality Solovay-Strassen jsou složitější varianty, které detekují všechny sloučeniny. Kterýkoli z těchto testů se používá, když je požadováno prvočíslo po co nejkratší době výpočtu, přičemž je akceptována malá míra pochybností, například v šifrování RSA nebo ve výměnném protokolu klíčů Diffie-Hellman .

Rychlé deterministické testy

Cyclotomic Test je deterministický test prvočíselnosti; dokážeme, že jeho doba realizace je O ( n zalepit (log (n)) ), kde n je počet číslic N a c je konstanta nezávislá na n . Jeho složitost je menší než polynomiální .

Lze prokázat, že test primality eliptické křivky běží na O ( n 6 ), ale pouze za použití některých domněnek teorie analytických čísel, které dosud nebyly prokázány, ale jsou široce přijímány jako pravdivé. V praxi je tento test pomalejší než cyklomtomický test pro čísla s více než 10 000 číslicemi.

Implementace těchto dvou metod je poměrně obtížná a riziko chyb v důsledku implementace je proto vyšší než u výše uvedených pravděpodobnostních metod.

Pokud je zobecněná Riemannova hypotéza pravdivá, lze Miller-Rabinův test převést na deterministickou verzi s dobou provedení Õ ( n 4 ). V praxi je tento algoritmus pomalejší než předchozí dva.

V roce 2002 popsali Manindra Agrawal, Neeraj Kayal a Nitin Saxena deterministický test prvočinnosti ( test prvočíselnosti AKS ), který probíhá v Õ ( č. 12 ). Navíc podle domněnky (neprokázané, ale obecně uznávané jako pravdivé) by bylo provedeno v Õ ( n 6 ). Jde tedy o první deterministický test primality doby polynomiálního provedení . V praxi je tento algoritmus pomalejší než ostatní metody.

Metody založené na teorii čísel

Teorie čísel poskytuje metody; dobrým příkladem je Lucas-Lehmerův test k otestování, zda je číslo prvočíslo. Tento test souvisí se skutečností, že multiplikativní pořadí určitého čísla a modulo n je n -1 pro prvočíslo n, když a je primitivní kořen . Pokud můžeme ukázat, že a je primitivní kořen pro n , můžeme ukázat, že n je prvočíslo.

Teorie složitosti

V teorii složitosti je problém PRIMES problémem rozhodování o příslušnosti k formálnímu jazyku, který obsahuje prvočísla, psaný binárně:

BONUS = {10, 11, 101, 111, 1011, ...}

kde 10, 11, 101, 111, 1011 ... jsou binární zápisy prvočísel 2, 3, 5, 7, 11 atd.

PRIMES je v co-NP  : jeho doplňkové KOMPOZITY, tj. Rozhodnutí patřit do množiny jiných než prvočísel, jsou v NP , protože můžeme rozhodnout o KOMPOZITECH v polynomiálním čase počtem číslic čísla, které má být testováno , na nedeterministickém Turingově stroji , uhodnutím faktoru.

V roce 1975 Vaughan Pratt  (en) ukázal, že existuje certifikát pro PREMIUM ověřitelný v polynomiálním čase. PRIMES je tedy také v NP, a tedy v NP ∩ coNP .

Algoritmy Solovay -Strassen a Miller-Rabin ukazují, že PRIMES je v coRP . V roce 1992 algoritmus Adleman - Huang ukázal, že PRIMES je v RP . PRIMES je tedy v ZPP = RP  ∩  coRP .

Test primality z roku 1983 Adleman - Pomerance - Rumely  (en) ukazuje, že PRIMES je v QP (kvazi-polynomiálním čase), což je třída, která nebyla ukázána, srovnatelná s jednou z výše uvedených tříd.

Test prvočíselnosti AKS je polynom čas algoritmus a konečně znázorňuje pojistné je v P . Ukázalo se však, že PRIMES není P-úplný . Nevíme, jestli je PRIMES například v NC nebo v LOGSPACE . Ale víme, že PRIMES není v AC 0 .

Poznámky a odkazy

  1. Vaughan Pratt. "Každý předseda má stručné vysvědčení". SIAM Journal on Computing , roč. 4, s. 214–220. 1975. Citace , plný text .
  2. Michael O Rabin , „  Pravděpodobnostní algoritmus pro testování primality  “, Journal of Number Theory , sv.  12, n o  1,1 st 02. 1980, str.  128–138 ( ISSN  0022-314X , DOI  10.1016 / 0022-314X (80) 90084-0 , číst online , přistupováno 9. července 2019 ).
  3. Adelman a Huang 1992 .
  4. Leonard M. Adleman , Carl Pomerance a Robert S. Rumely , „  O rozlišování prvočísel od složených čísel  “, Annals of Mathematics , sv.  117, n o  1,1983, str.  173–206 ( ISSN  0003-486X , DOI  10.2307 / 2006975 , číst online , přístup k 9. červenci 2019 ).
  5. „  QP v komplexu Zoo  “ .
  6. (en-US) „  PRIMES je v P | Annals of Mathematics  “ (přístup 9. července 2019 ) .
  7. Allender, Saks a Shparlinski 2001 .

Dodatky

Bibliografie

Tato kniha obsahuje mnoho algoritmů napsaných v Ruby . Prezentace tohoto vydání se liší od předchozího a je zaměřena na širší publikum.

Související články

externí odkazy