Texnalogiyalarini rivojlantirish vazirligi toshkent axborot texnalogiyalar unversiteti

O’ZBEKISTON RESPUBLIKASI AXBOROT
TEXNALOGIYALARINI RIVOJLANTIRISH VAZIRLIGI
TOSHKENT AXBOROT TEXNALOGIYALAR UNVERSITETI
QARSHI FILIALI ‘’TT VA KT’’ FAKULTETI

‘’AX 12-19’’ GURUHI TALABASI

‘’KRIPTOGRAFIYA 2” FANIDAN BAJARGAN

3-AMALIY ISHI

Qabul qildi: Bekkamov F
Tayyorladi: Sodiqov . F

3-amaliy ish
Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish
Ishdan maqsad: Diskret logarifmlash muammosi haqida haqidagi nazariy va amaliy bilim ko’nikmalarni shakllantirish.
Katta tub sonlarni generasiya qilishda hamda ularni tublikka sinashda algoritmning matematik yondashuvini inobatga olish kerak bo’ladi. Ko’rib chiqilgan algoritmlar orasida Rabbi-Miller testi katta sonlarni tublikka tekshirishda ehtimolan yondashib yakobi simvoli hamda lejandr xossalaridan kelib chiqib berilgan sonni tub yoki murakkab sonligini bir necha mezonlar bo’yicha aniqlaydi, bu esa uning bardoshliligini ta’minlab beradi
Kriptografiyada tub sonlar muhim ahamiyatga ega. Masalan, nosimmetrik tizimlarda faktorlash va diskret logarifmlash murakkabligiga asoslangan tizimlar ko’plab uchraydi va ular ochiq kalitli tizimlarning asosi hisoblanadi. Shularni hisobga olgan holda foydalaniyalayotgan katta uzunlikdagi tub sonlarni tublikka

Odatiy tub sonlarni hosil qilish algoritmi

tekshirish muhim ahamiyatga ega. Ushbu qismda tublikka tekshiruvchi testlar
asosida yaratilayotgan tub sonlarni tekshirish va ularni tubligini aniqlash masalasi ko’rib chiqiladi Odatiy holda foydalanilgan algoritm quyidagi rasmda ko’rsatilgan bo’lib, bunda, ana’viy usuldan foydalanilgan holatda agar tekshirilayotgan son kichik bo’lsa vaqtdan yutuq beradi, agar katta uzunlikka ega bo’lganda dasturning ishlash tezligi pasayib ketadi. Bunda quyidagi muammo orqali javob berish mumkin:
for (int i = 3; (i * i) <= candidate; i += 2)
{
if ((candidate % i) == 0)
{
return false;
}
}
Ushbu algoritmdan ko’rinib turibdiki agar sonning uzunligi oortib borsa, unda tekshirishlar soni ko’payadi va natijada vaqtdan yutqaziladi.
Taklif etilayotgan kompleks testlash usullari bo’yicha amalga oshirilib, bunda testlash usullaridan ixtiyoriy miqdorda foydalanish mumkin. Tublikka tekshirish testlari sonining ortishi bilan sarflanadigan vaqt ham ortib boradi.
Ushbu usulda testlar majmui quyidagi testlardan tashkil topgan:
- Fermaning kichik teoremasi;
- Rabin-Miller testi;
- Slovan-Shtrasset testi;
- Lukas strong testi.

Tub sonlarni hosil qilishning kombinasiyalashgan algoritmi

Yuqoridagi bo’limlarda assimetrik tizimlarni qurishda asos qilingan murakkablik turlari: etarli katta sonlarni tub ko’paytuvchilarga yoyish, Tub Tub emas Boshlanish Son Tamom True Testlash turlari xarakteristikasi etarli katta bo’lgan chekli maydonlarda diskret logarifmlarni hisoblash masalalarini echish murakkabliklari bilan bog’liq bo’lgan tizimlar ko’rib chiqildi. Zamonaviy kriptografiyada yangi hisoblangan, parametrli algebra murakkabliklarini kriptografik tizimga tadbiq etish katta yutuq beradi