Diskret logarifmlash algoritmlari va ularning dasturiy ta’minotini ishlab chiqish

Qadam. Quyidagi son hisoblansin

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

2. 
   Qadam. Quyidagi son hisoblansin
   

C 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) = 14
Bu qiymatlarni tartiblasak: 5,6,8,13,14.

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

v=1, 45(mod 17)=11
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.
u =5, v = 3.

6. 
   qadam. Javob :
   

x H*u – v (mod p-1)
ya’ni x 5*2 – 4(mod 16) = 6(mod 16) , x = 6.
x = 5*5 – 3(mod 16) = 25-3, x=22.
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.