Guruh talbasi Maxsudov Azamxon Yunusxo’ja o’g’li

642-20 guruh talbasi Maxsudov Azamxon Yunusxo’ja o’g’li

7- amaliy ish

Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish Faktorlash muammosini bartaraf etuvchi algoritmlar.

1. Faktorlash muammosi deb nimaga aytiladi
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¹⁶ 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. Ferma usuli. Quyidagi teorema tub ko‘paytuvchilarga ajratish algoritmini ifodalaydi hamda berilgan sonning tub ekanligini aniqlash imkonini beradi. Teorema. Aytaylik, n >1 toq son. Bu son murakkab son bo‘ladi faqat va faqat
^{ p,q}^{z+ bo’lib, n = p2 – q2=(p-q)*(p+q) bo‘lsa. Bu yerda p- q >1 . Ferma usulining mohiyati shundan iboratki, teorema natijasiga ko‘ra  p,q}^{z+ sonlar topish sonlar topish kerakki,}
n = p ² – q ² ; p ² = n+ q ² yoki q ² = n + p ² bajarilsin.
Agar p ² = n+ q ² , q =1,2,3……. qiymatlar uchun n+ q ² - son biror sonning to‘la kvadratidan iborat bo‘lmasa, u xolda q = (n -1)/2 qiymat uchun n+ q ² -ni tekshirib ko’riladi va biror sonning kvadratidan iborat bo’lsa. U holda n – tub son bo’adi. Misol. n =527 soni tub yoki tub emasligi aniqlansin.
2 Pollard usuli nimaga asoslanadi.
Pollard usuli. Ushbu usul Ro-algoritm yoki 𝜌 –algoritm nomlari bilan ham keng tarqalgan. Faktorlash muammosini yechishda takrorlanuvchi funksiya ketma-ketligidagi sikllarga va tugʼilgan kun paradoksiga asoslanadi. U ikki sonning koʼpaytmasidan tashkil topgan sonlarning faktorlash muammosini yechishda samarali. Uning murakkabligi 𝑂(𝑁^1/4) orqali baholanadi 𝜌 – algoritm sonlardan iborat ketma-ketlikni tashkil etadi va qaysidir 𝑛 sonidan boshlab siklni hosil qiladi. Hosil boʼlgan sikl 𝜌 koʼrinishida boʼlganligi uchun 𝜌 – algoritm deb nomlanadi. Kvadrat elak usuli (QSA) ham katta sonlarni faktorlash muammosini yechishga qaratilgan. U katta 𝑛 ^sonini √^{𝑛 gacha bo’lgan oraliqda tub kupaytuvchilarga ajratishda qoʼllaniladigan va 100 ta} oʼnlik sonlardan iborat katta sonlar uchun eng tezkor usul sanaladi. Algoritm ikki bosqichda amalga oshiriladi:1- bosqich. Maʼlumotlarni toʼplash. Ikki sonning kvadrati koʼrinishiga keltiriladigan sonlarni ajratib oladi. 2- bosqich. Maʼlumotlarni qayta ishlash. Barcha sonlarni matritsaga joylashtiradi va ikki sonning kvadrati koʼrinishidagi sonlarni olish uchun qayta ishlaydi.