2-ma’ruza Mavzu: Faktorlash muammosi va uni hisoblash; Qoldiq haqidagi Xitoy teoremasi; Sonni tub ko‘paytuvchilarga ajratish

Qoldiqlar haqida xitoy teoremasi. RSA, EL-GAMAl va boshqa asimmerik kriptotizimlarda ishtirok etuvchi parametrlarni ( masalan: , ye, d, R, Ya,Xa) topish jarayonida, x^u (mod z) taqqoslama qiymatini hisoblash kerak bo‘ladi. Qoldiqlar haqidagi Xitoy teoremasi qaralayotgan taqqoslamadagi z –sonini tub ko‘paytuvchilarga ajratib, keyin har bir taqqoslamani hisoblab, katta masala yechimini topish imkonini beradi. Quyida shu teorema va uning misollarga tadbiqlari haqida so‘z yuritamiz.
Teorema(Xitoy). Aytaylik m₁,m₂,….. m _n juft –jufti bilan o‘zaro tub sonlar bo‘lsin. U holda ixtyoriy butun a₁, a₂,…..a _n sonlar uchun
x a₁ (mod m₁) ,
x a₂ ( mod m₂ ),
…………………..
x a _n ( mod m _n)
taqqoslamalar sistemasi yagona yechimga ega bo‘lib, bu yechim:
x = ( M_j z_j )(mod M)
bu yerda, M_j =( m_i ) / m_j ;
z_j – esa quyidagi taqqoslama yechimi M_j z_j a_j (mod m_j ) har bir j – uchun va M = m₁m₂ ….m_n . Teorema isboti [5-9] keltirilgan.
MISOL 1. Shunday soni topingki uni 9; 11; 5 sonlariga bo‘lganda mos ravishda 5; 13; 7 qoldiqlar qolsin.
Masala shartiga muvofiq quydagicha tenglamalar sistemasini yechish zarur bo‘ladi:
x 5 (mod 9)
x 13 (mod 11)
x 7(mod 5)
Bunday taqqoslamalar sistemasi qoldiqlar haqida Xitoy teoremasiga muvofiq quyidagi tartibda yechiladi:
9*11*5 9*11*5 9*11*5
M₁= ----------- = 55 , M₂= ----------- = 45 , M₃=- ---------
9 11 5
M_j Z_j a_j (mod m_j) , j =1,2,3.
j=1 hol uchun, 55Z₁ 5 (mod 9), taqqoslama tenglama yechish qoidasiga ko‘ra:
55x+9u=5
55=9*6+1
9=1*9+0 ,
ya’ni EKUB (55,9)=1. demak, ular o‘zaro tub ekan. Kengaytirilgan Yevklid algoritmiga ko‘ra:
1=55 – 3*6 , yoki 55*1+9* 9 (- 6)=1 , u holda =1, = - 6
* 1*5
Z₁= -------------- = -------- = 5 . Z₁ 5 (mod 9)
EKUB (a,b) 1
j=2 hol uchun 45 Z₂ 13 (mod 11)
Xuddi yuqoridagidek, bu taqqoslamma yechimini ham topamiz:
45x+11u=13
45=11*4+1
11=11*1+0 ,
ya’ni EKUB (45,4)=1. Kengaytirilgan Yevklid algoritmiga ko‘ra:
45* (1)+11* (- 4)=1 =1, = - 4
demak, Z₂=1*13= 13 (mod 11).
j=3 hol uchun esa 99Z₃ 7(mod 5) taqqoslamani yechib:
99x+5u=7 ;
kengaytirilgan Yevklid algoritm muvofiq esa:
99=5*19+4
5=4*1+1
4=1*4+0 ,
ya’ni, EKUB (99,5)=1. Demak, Z₃= - 17= - 7 (mod 5) .
Shunday qilib, biz izlayotgan yechim:
x= (55*5+45*13+99*(-7))(mod (9*11*5)) = 167(mod 495).
JAVOB x 167(mod 495) .
Qoldiqlar haqidagi Xitoy teoremasida m₁,m₂,….. m _k o‘zaro juft –jufti bilan tub sonlar bo‘lmasa ham quyidagicha umumlashtirish mumkin[9].
Teorema 2. Taqqoslamalar sistemasi
x a₁ (mod m₁) ,
x a₂ ( mod m₂ ),
…………………..
x a _k ( mod m _k)
echimga ega bo‘ladi faqat va faqat
( a _I – a_j ) : EKUB( m_i , m_j ) 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 .