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


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


Download 0.8 Mb.
bet6/6
Sana27.01.2023
Hajmi0.8 Mb.
#1131330
1   2   3   4   5   6
Bog'liq
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.

Саволлар???


Download 0.8 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling