Farm test

Fermat -primalitetstesten i talteori  er en primalitetstest for et naturligt tal n baseret på Fermats lille sætning .

Indhold

Hvis n  er primtal , så opfylder det sammenligning for enhver a , der ikke er delelig med n .

At udføre en sammenligning er et nødvendigt, men ikke tilstrækkeligt, tegn på, at et tal er primtal. Det vil sige, hvis der er mindst én a for hvilken , så er tallet n  sammensat; ellers kan intet siges, selvom chancerne for, at tallet er prime stiger. Hvis der foretages en sammenligning for et sammensat tal n , så siges tallet n at være pseudoprimtal i basis a . Når man tester et tal for primalitet ved Fermats test, vælges flere tal a . Jo større antallet af a , for hvilket , jo større er chancen for, at tallet n er primtal. Der er dog sammensatte tal, for hvilke sammenligning udføres for alle et coprime til n  - disse er Carmichael-tal . Carmichael-tal er uendelige , det mindste Carmichael-tal er 561. Fermat-testen er dog ret effektiv til at detektere sammensatte tal.

Hastighed

Ved brug af hurtige eksponentieringsmodulo- algoritmer estimeres køretiden for Fermat-testen for en a til at være O (log 2 n  × log log n  × log log log n ), hvor n  er det tal, der testes. Normalt udføres flere kontroller med forskelligt a .

Litteratur

• Vasilenko O. N. Talteoretiske algoritmer i kryptografi, MTsNMO, 2003
• Trost E. - Primzahlen / Primtal - M .: GIFML, 1959, 135 sider
• Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein . Afsnit 31.8: Primalitetstest // Introduktion til algoritmer . - Anden version. — MIT Press; McGraw-Hill, 2001, s. 889-890. — ISBN 0-262-03293-7 . (Russisk)

Links

• Er dette tal primtal? // Berkeley Math Circle 2002-2003
• Fermats test // Algoritmer brugt i asymmetriske kryptosystemer. cryptowiki.net