2-Mavzu: Modulyar arifmetika Kriptologiya Kafedrasi katt o‘qit., Mardiyev U. R


Download 0.92 Mb.
bet1/4
Sana07.10.2023
Hajmi0.92 Mb.
#1694959
  1   2   3   4
Bog'liq
2.1-mavzu

2-Mavzu: Modulyar arifmetika

Kriptologiya Kafedrasi

katt.o‘qit., Mardiyev U.R.

Reja:

Evklid va kengaytirilgan Evklid algoritmi

  • Evklid algoritmini quyidagi ta’riflash mumkin:
  • va sonlarining eng katta umumiy bo‘luvchisini topish so‘ralgan bo‘lsin. Ushbu holda quyidagi ketma-ketlik amalga oshiriladi:
    • . Agar bo‘lsa, u holda ekanligi kelib chiqadi va bo‘ladi.
    • Agar bo‘lsa ni ga bo‘lib quyidagi tenglikni qanoatlantiradigan va butun sonlarga ega bo‘lamiz
    • . Agar bo‘lsa jarayon to‘xtaydi, ask holda oldingi qadamdek davom etadi

    • Ushbu jarayon qoldiq ga teng bo‘maguncha davom etadi. Aytaylik qadamda ga bo‘lindi va qoldiq ga teng bo‘lsa, ushbu hol uchun tengliklar quyidagi ko‘rinishda bo‘ladi:
      • .
      • .
      • .
      • .
  •  

Evklid va kengaytirilgan Evklid algoritmi

  • Hosil bo‘lgan nolga teng bo‘lagan qoldiqni ga teng deb ta‘kidlash mumkin bo‘ladi. Buni isboti quyidagi Lemmaga asoslanadi:
  • Agar bo‘lsa, u holda .
  • Misol: ni Evklid algoritmi bo‘yicha hisoblash kerak bo‘lsin.
  • Demak ga tent bo‘ladi.
  •  

Evklid va kengaytirilgan Evklid algoritmi

  • Evklid algoritmidan judayam ajoyib fakt kelib chiqadi: ni a va b ning chiziqli birikmasi sifatida ifodalanish mumkin. Ya’ni
  • bo‘ladigan va butun sonlar mavjud.

  • Masalan:
  • va ni topish usuli kengaytirilgan Evklid algoritmi deyiladi.
  • ni toppish uchun dastlab Evklid algoritmidan foydalaniladi so‘ng, kengaytirilgan Evklid algoritmini amalga oshirish oson bo‘ladi.

  • Download 0.92 Mb.

    Do'stlaringiz bilan baham:
  1   2   3   4




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