Эҳтимоллик тестлари
Download 174.02 Kb.
|
Эҳтимоллик тестлари
- Bu sahifa navigatsiya:
- Миллер – Рабин тести
Мисол 2. n=21 – сони туб ёки мураккаб эканлиги аниқлансин.
Ечиш. , , деб олсак. У ҳолда ЭКУБ(2;21)=1 шарт бажарилди, ; демак, , бу ердан эса тестга кўра, 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 – сони туб бўлади. Download 174.02 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling