Maatilan testi

Numeroteorian Fermat - primaliteettitesti  on luonnollisen luvun n primaliteettitesti , joka perustuu Fermatin pieneen lauseeseen .

Sisältö

Jos n  on alkuluku , niin se tyydyttää vertailun mille tahansa a :lle , joka ei ole jaollinen n :llä .

Vertailu on välttämätön, mutta ei riittävä merkki siitä, että luku on alkuluku. Eli jos on ainakin yksi a , jolle , niin luku n  on yhdistetty; muuten ei voida sanoa mitään, vaikka todennäköisyys, että luku on alkuluku, kasvaa. Jos vertailu tehdään yhdistelmäluvulle n , niin luvun n sanotaan olevan pseudoalkuluku kannassa a . Kun luvun primaalisuutta testataan Fermatin testillä, valitaan useita lukuja a . Mitä suurempi luku a , jolle , sitä suurempi on mahdollisuus, että luku n on alkuluku. On kuitenkin olemassa yhdistelmälukuja , joille vertailu suoritetaan kaikille n : n koprimeille  - nämä ovat Carmichael-lukuja . Carmichael-luvut ovat äärettömiä , pienin Carmichael-luku on 561. Fermat-testi on kuitenkin varsin tehokas yhdistelmälukujen havaitsemiseen.

Nopeus

Nopeita eksponentiomoduloalgoritmeja käytettäessä Fermat-testin suoritusaika yhdelle a :lle arvioidaan O (log 2 n  × log log n  × log log log n ), jossa n  on testattava luku. Yleensä suoritetaan useita tarkistuksia eri a .

Kirjallisuus

• Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa, MTsNMO, 2003
• Trost E. - Primzahlen / Alkuluvut - M .: GIFML, 1959, 135 sivua
• Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein . Osio 31.8: Primaalisuustestaus // Algoritmien johdanto . - Toinen painos. — MIT Press; McGraw-Hill, 2001, s. 889-890. — ISBN 0-262-03293-7 . (Venäjän kieli)

Linkit

• Onko tämä luku alkuluku? // Berkeley Math Circle 2002-2003
• Fermatin testi // Epäsymmetrisissä kryptojärjestelmissä käytetyt algoritmit. cryptowiki.net