7- amaliy ish Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish Faktorlash muammosini bartaraf etuvchi algoritmlar

Chekli gruppada diskret logarifmni hisoblash
Biz shu paytgacha chegirmalar nazariyasi bo’yicha tanishganimizda
a^x mod p ;
ifoda qiymatini topish bilan tanishgan edik.
Quyidagi masala esa oldingi masaladan ko’ra murakkabrok hisoblanadi, yani shunday x- butun son topilsinki :
a^x b (mod p) (1)
o’rinli bo’lsin. Bu yerda r-tub son va (1) tenglama (Z /pZ) gruppada qaralyapti

1. 
   tenglamaning yechimi x =log _a b - ni quyidagi formula orqali topish mumkin:
   

log _a b ( 1- a^j ) ^-1 b^j (mod p-1).
Biroq bu formula bilan yechimni topish masalasi bevosita «mumkin bo’lgan barcha xolatlarni ko’rib chiqish» kabi usulga o’xshash bo’lgani uchun ham amalda bu formula qo’llanilmaydi. Quyida keltiriladigan algoritm esa hisoblashlar sonini qisqartirib yechimni topishning samarali usulini beradi.
10-amaliy mashg’ulot
Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi algortim.
Diskret logarifmlash muammosini bartaraf etuvchi dasturni loyihalash
Ishdan maqsad:Diskret logarifmlash muammosi haqida haqidagi nazariy va amaliy bilim ko‘nikmalarni shakllantirish.
Nazariy qism
Cheklimaydondadiskretlogarifmlashmuammosi. chekli siklik guruh berilgan boʼlsin va . Tenglikdan х nomalum butun sonni topish lozim va .
.
Bu yerda, butun son asosga ko’ra ningdiskret logarifmi asosida hisoblanadiva u quyidagigatengbo’ladi:

Misol: chekli siklik guruh berilgan boʼlsin va . Tenglikdan x nomalum butun sonni topish lozim.
.
va,

Diskret logorifmlash muammosiga qarshi xujumlar. Koʼpchilik ochiq kalitli kriptotizimlar siklik guruhdagi diskret logarifmning hisoblash murakkabligiga asoslangan. Yaʼni, toʼplamda uchun ni hsoblash lozim:

Bu yerda, ayni bir guruhga tegishli. Diskret logarifmlash muammosiga qaratilgan hujumlar aynan uning hisoblash murakkabligiga asoslanadi. RSA algoritmi esa, faktorlash muammosiga asoslanadi.
Qoʼpol kuch hujumi (Brute-Force).Ushbu usul diskret logarifmni hisoblashning eng oson yoʼlini izlashga qaratilgan. soning darajasi soniga teng boʼlgancha quyidagicha hisoblanadi:
Tasodifiy x logarifmga ehtimolli x qiymatlarning yarmini hisoblash orqali erishishimiz mumkin. Бу kompleks natijasini berishi mumkin. Bu yerda, guruhning oʼlchami.
Ushbu hujumi oldini olish uchun guruh oʼlchamini katta tanlash lozim. Diffi-Helman kalitlarni almashish algoritmini oladigan boʼlsak, diskret logarifmni hisoblashning yarmiga teng boʼladi. Bu esa, hozirgi hisoblash texnologiyalari rivojlangan bir vaqtda ehtimoli mavjud.
Shenksning katta va kichik qadami (Baby-Step/ Giant-Step). Koʼp maʼlumolardan qoʼpol kuch qidiruvi uchun sarflanadigan vaqtni kamaytirishga qaratigan. qiymatini ikkita ifoda orqali tasvirlashga qaratilgan.
,
бу ерда .
qiymatiG guruhning kvadrat ildizi asosida hisoblanadi. Unda diskret logarifmni quyidagicha ifodalashimiz mumkin:


Аlgoritmning maqsadi va ni hisoblashga qaratilgan.
ni hisoblashga qaratilgan. ning barcha qiymatlarini hisoblaymiz va saqlab qoʼyamiz. Bu yerda, . Bu kichik qadam hisoblanib, qadamlarini oʼz ichiga oladi.
Katta qadamda esa, boʼlishi mumkin boʼlgan barcha sonlarini hisoblaydi. Bu yerda, .

kichik qadamda hisoblangan va saqlangan. juftligi uchun tenglik oʼrinli boʼlsa,

Agar guruh tartibiga ega boʼlsa, unda kichik qadam asosida hisoblashlar va hotira talab etiladi.
Polig-Xelman algoritmi. Ushbu algoritm G guruhdagi diskret logarifmning hisoblash tezligi oshirish maqsadida qoʼllaniladi. ord(g) g elementini saralashni amalga oshirishini hisobga olsak, , quyidagi tenglikni hisobga olish lozim. ва бўлса, унда .
Isboti. . Bu yerda, ni saralash koʼpi bilan bo’ladi. Agar bo’lsa, ga teng vaqsonig sonining saralangani sanaladi hamda mos holda, yoki shartlarni qanoatlantirilishi lozim.
Ushbu holatda qoldiqlar haqidagi xitoy teoremasidan foydalanish lozim. Аgar, barcha holatlar uchun va bo’lsa, unda
ва koʼrinishida ifodalanadi.Аlgoritmning hisoblash vaqti saralangan guruhdagi sonlarning tublik ehtimoliga bogʼliq. Ushbu hujumdan himoyalanish uchun oʼlchamidagi katta sonlardan foydalanish lozim. Аlgoritmning ahamiyatli jihati shundaki, u guruhdagi tub sonlarning faktorlash muammosini aniqlashga qaratilgan. Ushbu holatda elleptik egri chiziqlar samarali, ammo siklik guruhlarni saralash oson hisoblanadigan jarayon emas.