Эҳтимоллик тестлари

Чекли группада дискрет логарифни ҳисоблаш

Биз шу пайтгача чегирмалар назарияси бўйича танишганимизда

а^х mod р ;

ифода қийматини топиш билан танишган эдик.
Қуйидаги масала эса олдинги масаладан кўра мураккаброк ҳисобланади, яьни шундай х- бутун сон топилсинки :
а^х b (mod р) (1)
ўринли бўлсин. Бу ерда р-туб сон ва (1) тенглама (Z /pZ) группада қараляпти .

1. 
   тенгламанинг ечими x =log _a b - ни қуйидаги формула орқали топиш мумкин:
   

log _a b ( 1- а^j ) ^-1 b^j (mod p-1).
Бироқ бу формула билан ечимни топиш масаласи бевосита «мумкин бўлган барча холатларни кўриб чиқиш» каби усулга ўхшаш бўлгани учун ҳам амалда бу формула қўлланилмайди. Қуйида келтириладиган алгоритм эса ҳисоблашлар сонини қисқартириб ечимни топишнинг самарали усулини беради.


Дискрет логарифмлаш алгоритми:

1. 
   Қадам. Қуйидаги сон ҳисоблансин
   

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

2. 
   Қадам. Қуйидаги сон ҳисоблансин
   

С а^Н (mod p)
3- Қадам. u, 1 u H сонли қийматлари учун С^u (mod p) жадвал тузинг. Бу қийматларни тартиблаб чиқинг.
4 – Қадам. Кейинги жадвал эса b*а ^v (mod p) , 0 H қийматлар учун тузилиб тартиблансин.
5- Қадам. Биринчи ва иккинчи жадвалда тенг чиққан u, v элементлар олинсин.
6- Қадам. Жавоб сифатида
х Н*u – v (mod p-1)
олинсин.


Мисол 1. Қуйидаги

3^х 15 (mod 17)
ифодадан х- ни топинг.
Ечиш: Бевосита текшириб кўриш мумкинки, х= 6 бу тенгликни каноатлантиради . Ҳақиқатан 3⁶ = 729; 729 = 42*17 + 15 .
Шуни таъкидлаш керакки бизни фақат бутун ечимлар қизиқтиради. Шунинг учун ҳам (1) ифодадан бутун х-ни топиш масаласи мураккаб ҳисобланади.
Бу мисолни ечиш жараёни юқоридаги алгоритм орқали қуйидагича амалга оширилади.

1. 
   қадам. Н := [ p^1/2] +1 , Н= 5.
   
2. 
   қадам. С а^Н (mod p), С = 3⁵(mod 17) =5.
   
3. 
   қадам. 5^u (mod 17) , 1 u 5 жадвал қийматларини ҳисоблаймиз:
   

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
Бу қийматларни тартибласак: 5,6,8,13 .

4. 
   қадам. 15*3^v(mod 17) , 0 v 5 жадвал қийматларини ҳисоблаймиз :
   

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
Бу қийматларни тартибласак: 7,8,11,14,16.

5. 
   қадам. Иккита жадвал натижалари устма-уст тушган u, v –элементларни танлаб оламиз.
   

Яьни, u =2, v = 4.

6. 
   қадам. Жавоб :
   

х Н*u – v (mod p-1)
яьни х 5*2 – 4(mod 16) = 6(mod 16) , x = 6.
Мисол 2. Берилган ифодадан х –ни топинг
3^х 7 (mod 13).
Ечиш. Бевосита текшириб кўриш мумкинки бутун х-сони мавжуд эмас. Буни ҳам юқоридаги алгоритм орқали текширамиз : а = 3, b =7, p = 13

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