1- amaliy ish Mavzu: Openssl kutubxonasidan foydalangan holda maʼlumotlarni rsa algoritmi yordamida shifrlash. Ishdan maqsad

Topshiriq

1. 
   Tub sonlarni generatsiya qiladigan ( Delpi, Java, C++ va C# dasturlash tizimlaridan biridan foydalangan holda ) dasturiy vosita ishlab chiqilsin.
   
2. 
   Ferma usuli yoki Pollard usuli foydalangan holda N sonini tub ko‘paytuvchilarga ajrating
   

№	N
	5893
	3393
	3901
	4797
	7571
	5031
	8137
	6499
	6157
	7979
	4453
	2173
	3977
	2059
	5723
	5561
	4559
	4181
	3277
	5311
	3007
	3277
	4189

Nazorat savollari

1. 
   Faktorlash muammosi deb nimaga aytiladi
   
2. 
   Pollard usuli nimaga asoslanadi.
   

3-amaliy ish

Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish.
Ishdan maqsad: Diskret logarifmlash muammosi haqida nazariy va amaliy bilim ko‘nikmalarni shakllantirish.
Nazariy qism
Chekli maydonda diskret logarifmlash muammosi. chekli siklik guruh berilgan boʼlsin va . Tenglikdan x nomalum butun sonni topish lozim va .
.
Bu yerda, butun son asosga ko’ra ning diskret logarifmi asosida hisoblanadi va u quyidagiga teng bo’ladi:

Misol: chekli siklik guruh berilgan boʼlsin va . Tenglikdan x nomalum butun sonni topish lozim.
.
va,

Chekli gruppada diskret logarifmni hisoblash
Biz shu paytgacha chegirmalar nazariyasi bo’yicha tanishganimizda
a^x mod p ;
ifoda qiymatini topish bilan tanishgan edik.
Quyidagi masala esa oldingi masaladan ko’ra murakkabrok hisoblanadi, yani shunday x- butun son topilsinki :
a^x b (mod p) (1)
o’rinli bo’lsin. Bu yerda r-tub son va (1) tenglama (Z /pZ) gruppada qaralyapti

1. 
   tenglamaning yechimi x =log _a b - ni quyidagi formula orqali topish mumkin:
   

log _a b ( 1- a^j ) ^-1 b^j (mod p-1).
Biroq bu formula bilan yechimni topish masalasi bevosita «mumkin bo’lgan barcha xolatlarni ko’rib chiqish» kabi usulga o’xshash bo’lgani uchun ham amalda bu formula qo’llanilmaydi. Quyida keltiriladigan algoritm esa hisoblashlar sonini qisqartirib yechimni topishning samarali usulini beradi.
Diskret logarifmlash algoritmi:

1. 
   Qadam. Quyidagi son hisoblansin
   

H:= [p^1/2] +1

2. 
   Qadam. Quyidagi son hisoblansin
   

H a^H (mod p)
3- Qadam. u, 1 u H sonli qiymatlari uchun C^u (mod p) jadval tuzing. Bu qiymatlarni tartiblab chiqing.
4 – Qadam. Keyingi jadval esa b*a ^v (mod p) , 0 H qiymatlar uchun tuzilib tartiblansin.
5- Qadam. Birinchi va ikkinchi jadvalda teng chiqqan u, v elementlar olinsin.
6- Qadam. Javob sifatida
x H*u – v (mod p-1)
olinsin.
Amaliy qism
Misol 1. Quyidagi
3^x 15 (mod 17)
ifodadan x- ni toping.
Yechish: Bevosita tekshirib ko’rish mumkinki, x= 6 bu tenglikni qanoatlantiradi . Haqiqatan 3⁶ = 729; 729 = 42*17 + 15 .
Shuni ta’kidlash kerakki bizni faqat butun yechimlar qiziqtiradi. Shuning uchun ham (1) ifodadan butun x-ni topish masalasi murakkab hisoblanadi.
Bu misolni yechish jarayoni yuqoridagi algoritm orqali quyidagicha amalga oshiriladi.

1. 
   qadam. H := [ p^1/2] +1 , H= 5.
   
2. 
   qadam. C a^H (mod p), C = 3⁵(mod 17) =5.
   
3. 
   qadam. 5^u (mod 17) , 1 u 5 jadval qiymatlarini hisoblaymiz:
   

u =1, 5(mod 17) =5
u=2, 25(mod17) = 8
u=3, 125(mod 17)=6
u=4, 625(mod17) = 13
u=5, 3125(mod17) = 6
Bu qiymatlarni tartiblasak: 5,6,8,13 .

4. 
   qadam. 15*3^v(mod 17) , 0 v 5 jadval qiymatlarini hisoblaymiz :
   

v=1, 45(mod 17)=1
v=2, 15*9(mod 17) =16
v=3, 15*27(mod 17)= 14
v=4, 15*81(mod17)=8
v=5, 15*243(mod 17) = 7
Bu qiymatlarni tartiblasak: 7,8,11,14,16.

5. 
   qadam. Ikkita jadval natijalari ustma-ust tushgan u, v –elementlarni tanlab olamiz.
   

Yani, u =2, v = 4.

6. 
   qadam. Javob :
   

x H*u – v (mod p-1)
ya’ni x 5*2 – 4(mod 16) = 6(mod 16) , x = 6.
Misol 2. Berilgan ifodadan x – ni toping
3^x 7 (mod 13).
Yechish. Bevosita tekshirib ko’rish mumkinki butun x-soni mavjud emas. Buni ham yuqoridagi algoritm orqali tekshiramiz : a = 3, b =7, p = 13

1. 
   H := [ p^1/2] +1 , H= 4.
   
2.