8-amaliy mashg’ulot Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish

Sherman – Leman usuli
Aytaylik, n-juft bo‘lmagan va n > 8 butun son. Algoritm quyidagi qadamlardan iborat.
1-Qadam. Barcha a = 2,3,4………,[(n)^1/3 ] sonlar uchun n : a bajarilishi tekshirib ko‘riladi.
Agar qaysidir bir a – uchun n : a bajarilsa, u holda faktorizatsiya masalasi hal bo‘lib, algoritm qadami shu yerda to‘xtatiladi. Aks holda esa keyingi qadamga o‘tiladi.
2-Qadam. Barcha k = 1,2,3….[(n)^1/3 ] va d = 0,1,2,..... , [(n)^1/6 / (4* )] +1 uchun quyidagi son:
( [ ] +d )² – 4*k*n
biror sonning (natural) kvadrati bo‘ladimi, shuni tekshirish lozim. Agar shunday bo‘lsa, u holda
A= [ ] +d ; V= ;
uchun A² V² (mod n)
taqqoslama o‘rinli hamda quyidagi shart bajarilishi
1< EKUB (A V; n) < n;
tekshirish kerak.
Agar bu shart o‘rinli bo‘lsa, u holda berilgan n –sonini ikkita (tub) ko‘paytuvchiga ajratgan bo‘lamiz va algoritm o‘z ishini tugatadi.
Topshiriq
Katta son olib uni tub ko’paytuvchilarga ajrating.Pollard usuli yordamida Katta sonni tub ko’paytuvchilarga ajrating.
Hisobot quyidagi ma’lumotlardan tarkib topgan bo‘lishi lozim:
Nazariy qismda keltirilgan algoritmning dasturiy ta’minotidan foydalanish jarayonidagi olingan rasmlari va ularga izoh. Yaratilgan dasturiy ta’minotning dasturiy kodi.
Nazorat savollari
Faktorlash muammosi asoslari nimalardan iborat.
RSA shifrlash algoritmini tushuntiring.
El-Gamal shifrlash algoritmi ketma - ketligini ayting.
Kalitsiz RSA shifrlash algoritmini qanday tahlil qilish mumkin?

9-amaliy ish
Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish. Diskret logarifmlash muammosini bartaraf etuvchi algoritmlar
Ishdan maqsad: Diskret logarifmlash muammosi haqida nazariy va amaliy bilim ko‘nikmalarni shakllantirish.