Farmářský test

Fermatův test primality v teorii čísel  je test primality pro přirozené číslo n založený na Fermatově malé větě .

Obsah

 Je -li n prvočíslo , pak vyhovuje srovnání pro libovolné a , které není dělitelné n .

Provedení srovnání je nezbytným, ale ne dostatečným znakem toho, že číslo je prvočíslo. To znamená, že pokud existuje alespoň jedno a pro které , pak číslo n  je složené; jinak se nedá nic říct, i když šance, že číslo je prvočíslo, se zvyšuje. Pokud je provedeno srovnání pro složené číslo n , pak číslo n je považováno za pseudoprvo v základu a . Při testování čísla na primálnost Fermatovým testem se vybere několik čísel a . Čím větší je číslo a , pro které , tím větší je šance, že číslo n je prvočíslo. Nicméně, tam jsou složená čísla pro která srovnání je vykonáváno pro všechny coprime k n -  toto jsou Carmichael čísla . Carmichaelova čísla jsou nekonečná , nejmenší Carmichaelovo číslo je 561. Fermatův test je však docela účinný pro detekci složených čísel.

Rychlost

Při použití rychlých umocňovacích modulo algoritmů se doba trvání Fermatova testu pro jedno a odhaduje na O (log 2 n  × log log n  × log log log n ), kde n  je testované číslo. Obvykle se provádí několik kontrol s různými a .

Literatura

• Vasilenko O. N. Číselné teoretické algoritmy v kryptografii, MTsNMO, 2003
• Trost E. - Primzahlen / Prvočísla - M .: GIFML, 1959, 135 stran
• Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein . Oddíl 31.8: Testování primality // Úvod do algoritmů . - Druhé vydání. — MIT Press; McGraw-Hill, 2001, str. 889-890. — ISBN 0-262-03293-7 . (Ruština)

Odkazy

• Je toto číslo prvočíslo? // Berkeley Math Circle 2002-2003
• Fermatův test // Algoritmy používané v asymetrických kryptosystémech. cryptowiki.net