Diskret logarifmlash algoritmlari va ularning dasturiy ta’minotini ishlab chiqish

C a^N (mod p), C = 3 ⁴(mod 13) =3.

3^u (mod 13) , 1 u 4 jadval qiymatlarini hisoblaymiz:

u =1, 3(mod 17) =3
u=2, 9(mod17) = 9
u=3, 27(mod 17)= 10
u=4, 81(mod17) = 3

4. 
   7*3^v(mod 13) , 0 v 4 jadval qiymatlarini hisoblaymiz :
   

v= 0, 7 (mod 13) = 7
v=1, 21(mod 17)=4
v=2, 21*3(mod 17) =12
v=3, 7*27(mod 17)= 2
v=4, 7*81(mod17)= 4

5. 
   Ikkita jadval natijalari ustma-ust tushgan u, v –elementlarni tanlab olamiz. Biroq bunday qiymatlar mavjud emas ekan.
   
6. 
   Javob butun yechim yo‘q degan xulosaga kelamiz.
   

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


𝑎^𝑞 va 𝑏^𝑞 topulguncha, 𝑎₀ ni tanlash yo‘li bilan topamiz va 𝑥 = 𝑎₀ + 𝑎₁𝑝 topulguncha, keyin 𝑥 ≡ 𝑎₀ 𝑚𝑜𝑑 𝑝.
Xuddi shu yo‘l oqali 𝑥 ≡ 𝑏₀ 𝑚𝑜𝑑 𝑞 ni ham topamiz. Shundan so‘ng qoldiqlar
haqidagi Xitoy teoremasidan foydalanib 𝑥 ni topamiz.
Misol 3. (Polig-Xelman):
3^𝑥 ≡ 22 𝑚𝑜𝑑 31 ni topish talab etilsin.
Dastlab Eyler funksiyasini hisoblaymiz, 𝜑 (31) = 30, qaysiki faktorlari 30=5*6 teng bo‘lgan.
Deylik 𝑥 = 𝑎₀ + 5𝑎₁ bo‘lsin, bundan:




kelib chiqadi, 𝑎₀ ni qiymatini tanlash yo‘li orqali topamiz, bunda 𝑎₀ = 2, 𝑥 = 2 + 5𝑎₁ tenglikdan 𝑥 ≡ 2 𝑚𝑜𝑑 5 kelib chiqadi.
Keyingi son uchun: 𝑥 = 𝑏₀ + 5𝑏₁ bo‘lsin, bundan:




kelib chiqadi, yana tanlash yo‘li orqali 𝑏₀ ni qiymatini topamiz, bunda 𝑏₀ = 5, 𝑥 = 5 + 6𝑏₁ tenglikdan 𝑥 ≡ 5 𝑚𝑜𝑑 6 kelib chiqadi.
Demak:
𝑥 ≡ 2 𝑚𝑜𝑑 5
𝑥 ≡ 5 𝑚𝑜𝑑 6
Qoldiqlar haqidagi Xitoy teoremasidan 𝑥 = 17 kelib chiqadi. Yani:
Agar 𝑛_𝑖 o‘zaro tub son sonlar va 𝑎_𝑖 butun sonlar bo‘lsa 1 ≤ 𝑖 ≤ 𝑘. Shunday 𝑥 butun son topiladiki quyidagi tenglik o‘rinli bo‘ladi:
𝑥 ≡ 𝑎₁𝑚𝑜𝑑 m₁,
𝑥 ≡ 𝑎₂𝑚𝑜𝑑 m₂,
…
𝑥 ≡ 𝑎_𝑘𝑚𝑜𝑑 m_𝑘
Ushbu tenglikni yechish uchun quyidagi shartlar bajarilishi kerak:




Yechish:
𝑥 ≡ 2 𝑚𝑜𝑑 5
𝑥 ≡ 5 𝑚𝑜𝑑 6











X=17