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].