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

Mashqlar
№ 2. Quyidagilarni ko‘rsating
A) 7²⁰ 1 (mod 25);
B) 7²⁰ 1 ( mod 4) ;

3. 
   7²⁰ 1 ( mod 100).
   

№3 . Quyidagi qoldiqlarni hisoblang.
A) 3²⁷⁵ ( mod 100);
B) 6⁵⁰⁰⁰ (mod 1000);
C) 11²⁴⁶⁸¹ ( 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= v_m 2^m + v_m-12^m-1 +……..+ v₁2¹ + v₀ =[ v_m v_m-1 ….. v₁ v₀]₂
bu yerda v_i = 0 yoki 1 va v_m =1.
2-kadam. r_m = a (mod n) qiymatni yuklaymiz.
3-kadam. Barcha k = m-1, m-2, …..2,1 va k = 0 qiymatlar uchun



r_k+1² (mod n), agar v_k =0 bo‘lsa
r_k =
r_k+1² a (mod n), agar v_k =1 bo‘lsa.