Zbekiston respublikasi raqamli texnologiyalar

O’ZBEKISTON RESPUBLIKASI
RAQAMLI TEXNOLOGIYALAR
VAZIRLIGI

MUHAMMAD AL- XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNALOGIYALRI UNVERSITETI
KIBERXAVFSIZLIK FAKULTETI
713-21-GURUH CRY002-1-GURUH TALABASI
JUMAYEV JASURBEKNING
KRIPTOGRAFIYA FANIDAN
TAYYORLAGAN
LABARATORIYA ISHI

Bajardi: Jumayev J.
O’qituvchi: Xaitov N.

3. 
   amaliy ish.
   

Diskret logarifmlash algoritmlari va ularning dasturiy ta‘minotini ishlab chiqish.
5-Variant


Chekli gruppada diskret logarifmni hisoblash

Diskret logarifmlash algoritmi:

1- Qadam. Quyidagi son hisoblansin


2- Qadam. Quyidagi son hisoblansin


3-Qadam. u, H sonli qiymatlari uchun jadval tuzing. Bu qiymatlarni tartiblab chiqing.

4 – Qadam. Keyingi jadval esa , 0 H qiymatlar uchun tuzilib tartiblansin.

5- Qadam. Birinchi va ikkinchi jadvalda teng chiqqan u, v elementlar olinsin.
6- Qadam. Javob sifatida

olinsin.

10-variant misolini qo‘lda ishlanishi:
a = 16; b = 14; p = 53;

1. 
   qadam. H := [p^1/2] +1 = [53^1/2] + 1 = 8; H = 8;
   

2. 
   qadam. C = 16^8 (mod 53) = 42; C = 42;
   

3- qadam. , H jadval qiymatlarini hisoblaymiz:
u =1, 42^1(mod 53) =42
u=2, 42^2(mod 53) = 15
u=3, 42^3(mod 53)=47
u=4, 42^4(mod 53) = 13
u=5, 42^5(mod 53) = 16
u=6, 42^6(mod 53) = 36
u=7, 42^7(mod 53) = 28
u=8, 42^8(mod 53) = 10
4- qadam. , 0 H jadval qiymatlarini hisoblaymiz :
v=0, 14*16^0(mod 53)=14
v=1, 14*16^1(mod 53)=12
v=2, 14*16^2(mod 53)=33
v=3, 14*16^3(mod 53)=51
v=4, 14*16^4(mod 53)=21
v=5, 14*16^5(mod 53)=18
v=6, 14*16^6(mod 53)=23
v=7, 14*16^7(mod 53)=50
v=8, 14*16^8(mod 53)=5
Javob: u bilan v bir xil yechimga ega emasligi uchun yechimga ega emas.
Java dasturlash tilida bu misolni ishlanishi:
Dastur kodi:

public class Practicum3_Diskret {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int a, b, p, x, u = 0, v = 0;


System.out.print("a = ");
a = input.nextInt();
System.out.print("b = ");
b = input.nextInt();
System.out.print("p = ");
p = input.nextInt();
int H = (int) (Math.sqrt(p) + 1);
System.out.println("H = " + H);
int C = (int) (Math.pow(a, H) % p);
System.out.println("C = " + C);
System.out.println();
for (int i = 1; i <= H; i++) {
u = (int) (Math.pow(C, i) % p);
System.out.print("u(" + i + ")= " + u + ", ");
}
System.out.println();
for (int j = 0; j <= H; j++) {
v = (int) (b * Math.pow(a, j) % p);
System.out.print("v(" + j + ")= " + v + ", ");
}
System.out.println();
System.out.println();
for (int i = 1; i <= H; i++) {
u = (int) (Math.pow(C, i) % p);
for (int j = 0; j <= H; j++) {
v = (int) (b * Math.pow(a, j) % p);
if (u == v) {
x = H * i - (j % p);
System.out.println("x = " + + H + " * " + i + " - (" + j + " mod " + p + ")= " + x);
}
}
}
}
}


Javobi:


Polig-Xelman algoritmi (Pohlig-Hellman)

Eyler teoremasi:

Agar, 𝑎, 𝑚 o‘zaro tub sonlar bo‘lsa u holda bo‘ladi, bu yerda 𝜑(𝑚) – Eyler funksiyasi. 𝜑 𝑁 = 𝑝𝑞 teng bo‘lsin, EKUB 𝑝, 𝑞 = 1. 𝑎𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑝) ni yechish uchun Polig-Xelman algoritmi quyidagi yondashuvga asoslanadi. 𝑥 = 𝑎0 + 𝑎1𝑝 teng bo‘lsin.
Bundan

topulguncha, 𝑎0 ni tanlash yo‘li bilan topamiz va 𝑥 = 𝑎0 + 𝑎1𝑝 topulguncha, keyin 𝑥 ≡ 𝑎0 𝑚𝑜𝑑 𝑝.
Xuddi shu yo‘l oqali 𝑥 ≡ 𝑏0 𝑚𝑜𝑑 𝑞 ni ham topamiz. Shundan so‘ng qoldiqlar haqidagi Xitoy teoremasidan foydalanib 𝑥 ni topamiz.
5-variant.
14 mod 53;
Dastlab Eyler funksiyasini hisoblaymiz, 𝜑 (53) = 52, qaysiki faktorlari 52 = 13*4 teng bo‘lgan.
Deylik x = bo‘lsin, bundan
14^13mod 53;
14^13mod 53;
14^13mod 53;
52 mod 53;

kelib chiqadi, ning o’rniga qanday son qo’yishdan qat’iy nazar baribri yechimga ega emas.