Miller-Rabini test. *Fermat test: Fermat' teoreemist tulenevalt on teada, et kui p on algarv ja 1 < a < p, siis ap - 1 1 (mod p) ehk ap a (mod p). *Seega, et Fermat' testi abil kontrollida, kas naturaalarv n on kordarv või algarv: a).Kirjutan teatud hulga juhuslikult valitud aluste a = 2, 3 ,... n 1 baasil välja kongruentsi an- 1 1 (mod n). Kui antud kongruents osutub paari suvalise aluse korral kehtivaks, on suhteliselt tõenäoline, et n'i näol on tegu algarvuga. (Tõenäosus, et arv n on algarv on p(A) = 1 - 1/(2 s) *100% , kus s on erinvate katsete arv). b).Seega 10 katse õnnestumisel on eksimise tõenäosus juba väiksem, kui 0,01%. *Fermat' teoreemi miinused: 1. Mõningatel juhtudel on vaja arvutada väga suuri astmeid => võimalik siiski lahendada ruututõstmismeetodiga. 2. Vaja on arvutada väga suurte arvudega => appi tuleb modulaararitmeetika. 3
Tões tus : Et n pole algarv s iis s aame s elle es itada korrutis ena n= a*b, nii et a< n ja b< n. J uhul kui a ja b on algarvud, s iis on teoree m tões tatud, kui aga a või b pole algarv, s iis s aab s elle omakord a es itada kahe täis arvu korrutis ena j ne, kuni tule mus ena s aame algarvud. P rots ess on lõplik kuna igal s aamu l korrutis es olevad tegurid vähenevad. Teoree m. Kui n on mit tealg arv, s iis ta jagub algarvuga, mis on väiks em võrne n . Tões tus : Et n pole algarv, s iis j agub ta arvuga a, mis as ub vahemikus 1 < a < n K irj utame n= a*b J uhul kui a > n ja b > n s iis a * b > n * n = n mis on vale j äreldus s es t a*b= n. S eega on kas a n või s iis b n . J ärelikult arv n j agub arvuga mis on väiks e m võrdne n . S ee arv on kas algarv või j uhul kui pole s iis s aab s elle arvu es itada eel mis e teoreemi põhj al algarvude korrutis ena
Tões tus : Et n pole algarv s iis s aame s elle es itada korrutis ena n= a*b, nii et a< n j a b< n. J uhul kui a j a b on algarvud, s iis on teoree m tões tatud, kui aga a või b pole algarv, s iis s aab s elle omakord a es itada kahe täis arvu korrutis ena j ne, kuni tule mus ena s aame algarvud. P rots ess on lõplik kuna igal s aamu l korrutis es olevad tegurid vähenevad. Teoree m. K ui n on mi ttea lgarv, s iis ta j agub algarvuga, mis on väiks e m võrne n . Tões tus : Et n pole algarv, s iis j agub ta arvuga a, mis as ub vahe mikus 1 a n K irj utame n= a*b J uhul kui a n ja b n s iis a * b n * n n mis on vale j äreldus s es t a*b= n. S eega on kas a n või s iis b n . J ärelikult arv n j agub arvuga mis on väiks em võrdne n . S ee arv on kas algarv või j uhul kui pole s iis s aab s elle arvu es itada eel mis e teoreemi põhj al algarvude korrutis ena
Kas leidub mõni veel? Kuidas teda leida? Uus algarv ei tohiks kindlasti jaguda ühegagi juba teadaolevatest arvudest. Kõige lihtsam oleks siis vaadata arvu , mis on ühe võrra suurem kui kõikide seni leitud algarvude korrutis: Nii ei saa see arv kindlasti jaguda ühegagi juba leitud algarvudest, sest nendega jagamisel jätab ta jäägi 1. Kui see arv ei jagu enam ühegi teise arvuga peale ühe ja iseenda, ongi tegemist ühe uue algarvuga. Nüüd, kui tegemist ei ole algarvuga, siis nagu meenutasime, saab ta kirjutada erinevate algarvude korrutisena. Ükski neist algarvudest ei ole meile veel aga teada! Nii olemegi leidnud vähemalt ühe uue algarvu. Veelgi enam, ükskõik kui palju algarve me juba ei teaks, võime iga kord kasutada sama argumenti ja leida vähemalt ühe veel. Seega ongi algarve lõpmatult palju. Selle väite ja tõestuse peale olevat tulnud Eukleides, kuulus Vana-Kreeka matemaa-
annaabi.ee 
