Teorema 2. Taqqoslamalar sistemasi
x a1 (mod m1) ,
x a2 ( mod m2 ),
…………………..
x a k ( mod m k)
echimga ega bo‘ladi faqat va faqat
( a I – aj ) : EKUB( mi , mj ) barcha I, j , 1 I < j k .
Agar yechim mavjud bo‘lsa, u holda yagonadir.
Misol 2. Sistema yechimini toping:
x 5 (mod 6 ),
x 3 ( mod 10 ),
x 8 (mod 15).
Yechish :
Birinchi taqqoslamaga etibor qilsak:
x 5 ( mod 6 ), x = 5 + 6 * t .
Bu yechimni ikkinchi taqqoslamaga qo‘yib 5 + 6 * t 3 ( mod 10 ), yoki 6 * t 8 ( mod 10 ) va t 3 ( mod 10 ) . Shuning uchun t = 3 + 10 u . Bu oxirgi tenglikni uchinchi taqqoslama tenglamaga qo‘yib :
3 + 10 u 8 (mod 15)
yoki u 2 (mod 15) . U holda u = 2 + 15 v va
t = 3 + 10 ( 2+ 15 v) = 23 + 150 v ,
x = 5 + 6( 150 v +23 ) = 203 + 6*150 v ,
Shuning uchun javob: x = 203 .
Mashqlar
№ 2. Quyidagilarni ko‘rsating
A) 720 1 (mod 25);
B) 720 1 ( mod 4) ;
720 1 ( mod 100).
№3 . Quyidagi qoldiqlarni hisoblang.
A) 3275 ( mod 100);
B) 65000 (mod 1000);
C) 1124681 ( mod 83).
№4. Taqqoslamalar sistemasi yechimi topilsin.
A) x 5 (mod 6)
x 3 (mod 10)
x 8 (mod 15)
B) ) x 7 (mod 17)
x 9 (mod 13)
x 3 (mod 12)
C) x 5 (mod 9)
x 13 (mod 11)
x 7 (mod 5)
a^e (mod n) qoldiqni hisoblashning effektiv usuli
RSA , EL-GAMAL asimmetrik kriptotizimlarda malumotlarni shifrlash, deshifrlash va bu shifrlash algoritmlari bilan bog‘liq bo‘lgan boshqa parametrlarni hisoblash uchun a^e (mod n) taqqoslamani hisoblashga to‘g‘ri keladi. Agar berilgan a, ye, n sonlar katta razryadli sonlardan iborat bo‘lsa, a^e (mod n) taqqoslamani hisoblash masalasi hatto eng zamonaviy kopyuterlarda ham ancha mushkul hisoblanadi. Anashu maqsadda bunday taqqoslamalarni hisoblashning effektiv usullarini bilish muhimdir. Shunday algoritmlardan biri haqida to‘xtalib o‘tamiz.
Algoritm quyidagi qadamlardan iborat :
1-kadam. ye –soni ikkilik sanoq sistemasiga o‘tkaziladi:
e= vm 2m + vm-12m-1 +……..+ v121 + v0 =[ vm vm-1 ….. v1 v0]2
bu yerda vi = 0 yoki 1 va vm =1.
Do'stlaringiz bilan baham: |
