Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish

Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Kiberxavfsizlik fakulteti

Kriptografiya-2 fanidan

2-Amaliy ish

Bajardi:Axmadjonov A’zamjon
Tekshirdi:Mardiyev Ulug’bek

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.
Faktorlash - bu biror sonni tub ko‘paytuvchilarga ajratish jarayonidir.Faktorlash muammosini bartaraf etuvchi algoritmlar ishlab chiqilgan.Masalan,Ferma,Pollard,
Lenstr,Leman va boshqalar.Bular orasidan biz Ferma va Pollard usullarini ko’rib chiqamiz.
1.Ferma usuli.Bu usul Ferma teoremasiga asoslangan.Ferma teoremasining mohiyati shundan iboratki, 1 dan katta n soni uchun n=p²-q² shart bajarilsa n soni murakkab son bo‘ladi.Shu teoremadan foydalanib o’zimizning variantimizni ishlaymiz.
Variant raqami-4. Bunda n=4797.Variantni ishlashdan oldin n=p²-q² tenglikni p²= n+ q² ko’rinishiga keltiramiz.Bunda p soni topib olinadi.Buning uchun n soni 70 sonining kvadratidan kichik ekanligini bilgan holda p sonini aynan 70 va undan yuqori sonlardan tanlab olinadi.Shunda bizda p va n sonlari ma’lum bo’ladi.Keyin esa p²- n ayirma qandaydir sonning kvadrati bo’lguncha p sonini 70 dan boshlab bir birlik ko’tarib boraveramiz.Shunda quyidagi jadval hosil bo’ladi.