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

, bunda

qiymatini hisoblab olamiz

Barcha va qiymatlar ucun

Oldingi qadamning oxirgi natijasi ni yechimi sifatida olinadi.

Misol:

, bunda

Demak algoritmga muvofiq

•  

Katta darajali sonlarni modu bo‘yicha qoldig‘ini topishning effektiv usuli

• Qiymatlar quyidagi qoida asosida hisoblanadi

Javob:

•  

Katta darajali sonlarni modul bo‘yicha qoldig‘ini topishning effektiv usuli

• Misol 1:
• ;

•  

Qoldiqlar haqidagi Xitoy teoremasi

• Agar o‘zaro tub sonlar va butun sonlar bo‘lsa . Shunday butun son topiladiki, quyidagi tenglik o‘rinli bo‘ladi:
• Ushbu tenglikni yehish uchun quyidagi shartlar bajarilishi kerak:
• , yoki
• , bunda - quyidagi taqqoslama yechimi hisoblanadi

•  

Qoldiqlar haqidagi Xitoy teoremasi

• Misol: Shunday sonni topingki uni sonlariga bo‘lganda mos ravishda qoldoqlar qolsin.
• Masala shartlariga muvofiq quyidagi tenglamalar sistemisini yechish zarur bo‘ladi:

, bundan kelib chiqadi

, bundan kelib chiqadi

, bundan kelib chiqadi

, bundan kelib chiqadi

•  

• ni toppish uchun quyidag formula asosida hisoblab olamiz
• d

•  

Savollar???