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

Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish Faktorlash muammosini bartaraf etuvchi algoritmlar.
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, . 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 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 ( 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 = p² – q²=(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’ladi.