Эҳтимоллик тестлари

Мисол 2. n=21 – сони туб ёки мураккаб эканлиги аниқлансин.
Ечиш. , , деб олсак. У ҳолда

1. 
   ЭКУБ(2;21)=1 шарт бажарилди,
   
2. 
   
   

; демак, ,
бу ердан эса тестга кўра, n=21 – сони мураккаб сон деган хулосага келамиз.
Қуйида эса юқоридаги тестдан ҳам эффективроқ бўлган Миллер – Рабин тести деб аталувчи тест билан танишиб чиқамиз.
Теорема 2. n – тоқ мураккаб сон бўлсин, (яъни n – сони 3 – га бўлинмасин).
.
Бу ерда , t – тоқ сон. У ҳолда шартни ҳамда
ёки бирор j; лар учун қаноатлантирувчи - лар сони n/4 –дан ошмайди.
Натижа. Теорема 2 – дан худди теорема 1 – дан чиққан натижага ўхшаш эҳтимоллик тести туб бўлиш ёки бўлмаслиги учун натижа ҳосил қилиниб, агар k – та тасодифий - нинг қийматлари учун n – соннинг мураккаб эмас эканлиги аниқланса, у ҳолда берилган n – сони - эҳтимоллик билан туб сон деб юритилади.
Мисол 3. n=341 сонининг туб ёки туб эмаслиги текширилсин.
Ечиш. - бўлинмайди, чунки 3+4+1=8 3.
n-1=340, , яъни r =2, r 1, t=85 – тоқ сон.
У ҳолда , қаноатлантирувчи, қиймат учун
- шартни текширамиз.

ёки j: , бўлади ва:
демак, шартларимиздан бири бузилди. У ҳолда тестга мувофиқ n=341 – мураккаб сон экан.
Масалан,j=2 ҳолда ҳам; демак , бу ҳолда ҳам шарт бузилди.
Шундай қилиб, n=341 – мураккаб сон экан деган хулосага келамиз.
Мисол. n=1061 сонининг туб ёки туб эмаслиги аниқлансин.
Ечиш. бўлинмайди.
n-1=1060, ;
яъни r=2, t=265 – тоқ сон. У ҳолда шартлар бажарилишини текширамиз: , , .

яъни чиқди, лекин қолган - лар учун ҳисоблаб бевосита ишонч ҳосил қилиш мумкинки берилган n=1061 – сони туб бўлади.