- k=2,
- оралиқдан тасодифий a=5 танлаймиз.
- ЭКУБ(а,р)= ЭКУБ(5,19)=1
- Демак, шартни бажарилишини текширамиз.
- Таққосласак, демак, , .
- Бундан қуйидагича хулосага келиш мумкин: 19 сон 1-2-2 эҳтимоллик билан туб сон бўлади.
Рабин – Миллернинг катта сонларни тубликка синаш тести ҳозирги кунда носимметрик криптотизимларда модул ҳосил қилишда кенг қўлланилади. Бу алгоритм кучли псевдотуб сонларни синаш алгоритми сифатида тан олинган. У n -1 ни, яъни модулни битта камайтирилган қийматини 2s*r кўринишда ифодалашга асосланган. Бунда s ─ n -1 ни иккига бўлинишлар сони, r – тоқ сон. “n - сони тубми?” деган саволга, “туб” ёки “мураккаб” деган жавоб олишга қаратилган бўлади. - n -1 = 2s*r кўринишда ёзиб олинади, бунда r - тоқ сон;
- шартни қаноатлантирувчи а сон тасодифий танланади;
- ни ҳисобланади;
- Агар (у=1 ёки у=n -1) бўлса, у ҳолда кейинги итерацияга ўтиш.
- ҳисобланади;
- ;
- Агар (у=1) бўлса, у ҳолда “мураккаб сон” қайтарилади;
- Агар бўлса, у ҳолда “мураккаб сон” қайтарилади;
- Акс ҳолда “Туб сон” қайтарилади.
Рабин-Миллернинг катта сонларни тубликка синаш алгоритми - 4033-мураккаб сонини Рабин-Миллер алгоритмидан фойдаланиб тубликка синаймиз.
- 4033-1=63∙26
- 2 асосга кўра Рабин-Миллер алгоритмини қўллаймиз
- y=263 (mod 4033)≡3521(mod 4033)
- s=1 y=y2=35212 (mod 4033)=-1(mod 4033)
- Тест тугади, энди 3 асос билан текшириб кўрамиз.
- y=363 (mod 4033)≡3551(mod 4033)
- s=1 y=y2=35512 (mod 4033)=2443(mod 4033)
- s=2 y=y2=24432 (mod 4033)=3442(mod 4033)
- s=3 y=y2=34422 (mod 4033)=2443(mod 4033)
- s=4 y=y2=24432 (mod 4033)=3442(mod 4033)
- s=5 y=y2=34422 (mod 4033)=2443(mod 4033)
- Демак, берилган сон мураккаб.
Асосий ва қўшимча адабиётлар учун тавсиялар - Асосий адабиётлар
- Christof Paar·Jan Pelzl. Understanding Cryptography: A Textbook for Students and Practitioners. Verlag Berlin Heidelberg 2010.
- Keith M. Martin. Everyday Cryptography Fundamental Principles and Applications. United Kingdom, 2017
- Қўшимча адабиётлар
- Акбаров Д. Е. “Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланилиши” – Тошкент, 2008 – 394 бет.
- Stamp Mark. Information security: principles and practice. USA, 2011.
Саволлар???
Do'stlaringiz bilan baham: |