1-Мавзу: Туб сонлар ва уларни генерациялаш усуллари Криптология кафедраси

Соловэй-Штрассеннинг катта сонларни тубликка синаш алгоритми

• 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.

Саволлар???