Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish Faktorlash muammosini bartaraf etuvchi algoritmlar

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.