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

•  

Evklid va kengaytirilgan Evklid algoritmi

• Misol: . Bu yerda va ?.
• ekanligi kelib chiqadi.

•  

Evklid va kengaytirilgan Evklid algoritmi

• Demak

kelib chiqadi.

• Bunda va ga teng.
• Shuni e’tiborga olish kerakki bu usul sonini va ning chiziqli birikmasi sifatida ifodalashning yagona usuli emas. Boshqa imkoniyatlar qatorida biz 3054 · 12378 ni qo'shishimiz va ayirishimiz mumkin.

•  

Modulyar arifmetika

• Modul yoki soat arifmetikasi

va lar uchun qoldiqni ifodalab, natijasidagi qoldiqga teng bo‘lgan son nazarda tutiladi.

• Misollar

•  

Modulyar arifmetika

• Modulyar arifmetikaning xossalari:

Qo‘shish xossasi.

Ko‘paytirish xossasi.

• Manfiy sonni moduli

ning qo‘shishga teskarisi kabi belgilanib, uning natijasi ga qo‘shilganda bo‘lishi kerak.

va

• Modul bo‘yicha sonni teskarisni toppish

ning ko‘paytirishga teskarisi kabi belgilanib, uning natijasi ga ko‘paytirilganda ga teng bo‘lishi kerak.

va

•  

Modulyar arifmetika

taqqoslama uchun quyidagi xossalar o‘rinli

• Bir xil modulli taqqoslamalarni hadlab qo‘shish va ayirish mumkin:
• Taqqoslamaning bir qismidagi sonni ikkinchi qismiga qarama qarshi ishora bilan o‘tkazish mumkin:

•  

Modulyar arifmetika

• Taqqoslamani ixtiyoriy qismiga modulga karalla sonni qo‘shish mumkin: