ITT0030 Diskreetne matemaatika II - eksamikonspekt
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. Arv p võib osutuda pseudoalgarvuks => selle probleemi lahendamiseks tuleb a
valida juhuslikult ning Fermat' testi rakendada korduvalt.
4. Arv a võib osutuda Carmichaeli arvuks => Fermat' testi puhul ainuke
möödapääsmatu probleem; sellest tulebki rakendada efektiivsemad meetodeid nagu nt.
Miller-Rabini test.
*Miller-Rabini test:
*Miller-Rabini test on sisuliselt Fermat' teoreemi karastatud versioon, mis peaks olema
immuunne ka Carmichaeli arvude vastu:
annaabi.ee 
