Kriptologiya

O'ZBЕKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKЕNT AXBOROT TЕXNOLOGIYALARI UNIVЕRSITЕTI
“KRIPTOLOGIYA” kafedrasi


Kriptografiya2 fani bo`yicha
2-Amaliy ish.

Tekshirdi: Olimov I

Bajardi: Iskandarov A
Guruh: CRY003-1


TOSHKENT 2022

2-Amaliy ish.
Mavzu: : Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish.

Ishdan maqsad: Faktorlash muammosini bartaraf etish chora tadbirlari to’g’risida nazariy va amaliy ko‘nikmalarga ega bo‘lish.

Nazariy qism

Faktorlash 𝑛 sonini tub koʼpaytuvchilarga ajratish jarayoni. Masalan, 525 = 5 ∙ 5 ∙ 3 ∙ 7. Faktorlash murakkab hisoblashga ega vazifa sanaladi. Kriptografiyada RSA shifrlash algoritmida, elleptik egri chiziqlarda va kvant kriptografiyasida qoʼllaniladi. Faktorlash murakkablik darajasiga koʼra ikki turga ajratiladi: Eksponent va subeksponent. Eksponent algoritmlar (√𝑛𝑙𝑜𝑔2 𝑛) yoki 𝑂(√𝑛𝑙𝑜𝑔 𝑛) ni hisoblash murakkabligiga asoslanadi. Bu yerda, faktorlanadigan 𝑛 sonini 1 dan √𝑛 gacha ketma-ket boʼlish talab etiladi. Odatda tub sonlar jadvali olinadi va katta sonlarni (2 16 gacha) tekshirish amalga oshiriladi. Juda katta sonlarda qoʼllanilishi hisoblash tezligini pasayishiga olib keladi. Yuqorida keltirilgan Boʼluvchilarni tahmin qilish usuli, Ferma, Pollard, Lenstr, Leman va boshqa shu kabi usullarni keltirish mumkin va ular asosida faktorlash muammosini yechish mumkin.
Bu amaliy ishda Java dasturlash tilidan foydalangan holda faktorlash algoritmlari bajarildi.
Main classda ikkala algoritmlar chaqirildi:

Ferma usuli. Quyidagi teorema tub ko‘paytuvchilarga ajratish algoritmini ifodalaydi hamda berilgan sonning tub ekanligini aniqlash imkonini beradi.


Pollard usuli. Ushbu usul Ro-algoritm yoki 𝜌 –algoritm nomlari bilan ham keng tarqalgan. Faktorlash muammosini yechishda takrorlanuvchi funksiya ketmaketligidagi sikllarga va tugʼilgan kun paradoksiga asoslanadi.

Bajarilishi :

Algoritmni tanlaymiz

Ferma faktorlash : 5- variant bo’lganim uchun 7571 sonni kiritamiz :

Javob : 67 , 113

Pollard faktorlash : 5- variant bo’lganim uchun 7571 sonni kiritamiz :

Javob : 67 , 113