Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish

p	p^2= n+ q^2
q^2
70	70^2=4797+q^2	q^2=103 ?
71	71^2=4797+q^2	q^2=244 ?
72	72^2=4797+q^2	q^2=387 ?
73	73^2=4797+q^2	q^2=532 ?
74	74^2=4797+q^2	q^2=679 ?
75	75^2=4797+q^2	q^2=828 ?
76	76^2=4797+q^2	q^2=979 ?
77	77^2=4797+q^2	q^2=1132 ?
78	78^2=4797+q^2	q^2=1287 ?
79	79^2=4797+q^2	q^2=1444=38^2 ✓

Bundan kelib chiqadiki, n soni ya’ni 4797, 79²-38² ayirmaga ega bo’ladi.Ayirmani esa o’z o’rnida qisqa ko’paytirish formulasi orqali ifodalansa (79-38)*(79+38) ko’paytma hosil bo’ladi.Demak, n=4797 soni 41 va 117 sonlarining ko’paytmasiga teng va tub son emasligi isbotlandi.

n=4797=41*117
2.Pollard usuli.Pollard usuli Ro-algoritm nomi bilan ham ataladi.Bu usul faktorlash muammosini yechishda takrorlanuvchi funksiya ketma-ketligidagi sikllarga asoslanadi.Bunda x₀=y₀=2, F(x)=(x²+1)modn, n=4797.Dastlabki qiymatlarni va funksiyani qabul qilamiz.
i=1 holatda: F(x)=(x²+1)mod4797 formuladan X₀=F(x_1-1=0) ni topsak javob X₁^­­=5 javobi chiqadi va jadvalga yozamiz.
i=1 holatda: F(x)=(x²+1)mod4797 formuladan Y_i=F(F(y_1-1=0)) ni javobi 26 chiqadi.Buni ham jadvalga yozib olamiz.
i=1 holatda: EKUB(|x_i- y_i|,4797) ning javobini hisoblasak EKUB(|5- 26|,4797) -> 21 va 4797 sonlarining EKUB i o’zaro tub bo’lganligi uchun 1 bo’ladi.Buni ham jadvalga yozib olamiz.Xuddi shunday tartibda qolgan amallarni bajaramiz.

n=4797, F(x)=(x^2+1)mod4797, x0=y0=2
i	Xi=F(xi-1)	Yi=F(F(yi-1))	EKUB(|xi- yi|,4797)
1	5	26	1
2	26	2615	3

Ikkinchi qadamda EKUB da chiqqan qiymat 1 dan farqli bo’lganligi uchun EKUB dagi qiymat bizga berilgan n=4797 ning bitta tub ko’paytuvchisi bo’ladi,ya’ni,

n=4797=3*1599
Kelib chiqqan n₁=1599 sonini tub yoki murakkab ekanligini bilmaganimiz uchun bu sonni yana Pollard usulida tublikka tekshirib olamiz.

n=1599, F(x)=(x^2+1)mod1599, x0=y0=2
i	Xi=F(xi-1)	Yi=F(F(yi-1))	EKUB(|xi- yi|,1599)
1	5	26	1
2	26	1016	3

Yana ikkinchi qadamda EKUB da chiqqan qiymat 1 dan farqli bo’lganligi uchun EKUB dagi qiymat bizga berilgan n₁=1599 ning bitta tub ko’paytuvchisi bo’ladi,ya’ni,

n₁=1599=3*533
Yuqoridan kelib chiqqan n₂=533 soni ham bir qarashda tub yoki murakkab ekanligini bilish qiyin.Shuning uchun bu sonni ham yana tublikka tekshiramiz.

n=533, F(x)=(x^2+1)mod533, x0=y0=2
i	Xi=F(xi-1)	Yi=F(F(yi-1))	EKUB(|xi- yi|,533)
1	5	26	1
2	26	483	1
3	144	247	1
4	483	210	13

Bu yerda esa 4-qadamda EKUB 1 dan farqli chiqdi.Demak, 13 soni n₂=533 sonining tub ko’paytuvchisi ekanligi ma’lum bo’ldi.

n₂=533=13*41
Yuqoridagilardan ma’lum bo’ladiki,13 va 41 tub sonlar,demak, n=4797 sonining tub ko’paytuvchilari quyidagilardan iborat bo’ladi:
n=4797=3*3*13*41
Xulosa:
Biz ushbu amaliy ishda faktorlash muammosini yechish uchun qo’llaniladigan Ferma va Pollard usullarini ko’rib chiqdik.Xulosa o’rnida shuni aytish mumkinki,ikkala usulning ham o’ziga yarasha qulayliklari bor.Ferma usulida n=4797 sonini 41 va 117 ko’paytuvchilarga ajraldi.Ferma va Pollarda usullarida bir xil javob chiqmaganligini sababi 117 soni 3,3 va 13 tub ko’paytuvchilarga ajralishini ko’rish mumkin.Demak, natijalardan ko’rish mumkinki ikkala usulda ham bir xil javob chiqadi.Endi qaysi usul samarali ekanligiga kelsak,meni fikrimcha Pollard usuli samaraliroq.Chunki,Pollard yoki Ro-algoritmining mohiyati shundan iboratki u faqat murakkab sonning bitta tub ko’paytuvchisini aniqlaydi.Keyingi tub ko’paytuvchisini esa sonning o’ziga bo’lib topib olish mumkin.Bunda esa RSA algoritmidagi N=p*q ko’paytmadagi faktorlash orqali p va q sonlarini topib olish nisbatan tezroq amalga oshiriladi.Natijada RSA algoritmi yordamida shifrlangan malumotni kriptotahlil qilish osonroq bo’ladi.