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

Bir xil modulli taqqoslamalarni hadlab ko‘paytirish mumkin:

Taqqoslamani modulini o‘zgartirmagan holda taqqoslamani ikkala qismini bir xil butun songa ko‘ytirish mumkin:

Taqqoslamani modulini o‘zgartirmagan holda taqqoslamani ikkala qismini bir xil butun darajaga ko‘tarish mumkin:

Taqqoslamani ikkala qismini modul bilan o‘zaro tub bo‘lgan ko‘paytuvchiga qisqartirish mumkin:

, bunda

•  

Modulyar arifmetika

• Yagona yechimga ega
• Yechimga ega emas
• 11 ta yechimga ega

•  

Modulyar arifmetika

• Modulyar arifmetika bo‘yicha misollar

•  

Modulyar arifmetika

• Agar va soni ga bo‘linsa, u holda yechimlar soni ta bo‘ladi.
• .
• .

•  

Diafant tenglamalar

• Teorema: chiziqli Diafant tenglama yechimga ega bo‘ladi, agar faqat va faqat bo‘lganda, bu yerda . Agar va bu tenglamani har qanday maxsus yechimi bo‘lsa, boshqa barcha yechimlar

va orqali topiladi, bu yerda ixtiyoriy butun son.

• Misol: chiziqli moslikni yechish talab etilsin.

Evklidni kengaytirilgan algoritmi asosida

.

• Qolgan yechimlar va orqali topiladi.

•  

Diafant tenglamalar

• Misollar:

•  

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

• ni natijasini hisoblash talab etilsin
• Dastlab sonini ikkilik sanoq tizimiga o‘tkaziladi: