Faktorlash n sonini tub ko paytuvchilarga ajratish jarayoni. Ferma usuli

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti

Kiberxavfsizlik fakulteti III bosqich CRY001-1- guruh talabasi Keldiyorov Mansurning kriptografiya 1 fanidan 6-amaliy ishi Mavzu:Faktorizatsiyalash algoritmlari va ularning dasturiy ta’minotini ishlab chiqish

Bajardi: Keldiyorov Mansur

Tekshirdi: Mardiyev Ulug’bek

Toshkent 2023

Faktorlash n sonini tub ko paytuvchilarga ajratish jarayoni.
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 – q 2=(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 2 – q 2 ; p 2 = n+ q 2 yoki q 2 = n + p 2 bajarilsin.

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. 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.
5-varyant.
N=7571
𝐹(𝑥) = (𝑥² + 1)𝑚𝑜𝑑𝑛 𝑥₀ = 𝑦₀ = 2

i	𝑥i = 𝐹(𝑥i−1)	𝑦i = 𝐹(𝐹(𝑥i−1 ))	𝐸𝐾𝑈𝐵(|𝑥i – 𝑦i |, n)
1	5	26	gcd(26-5, 7571) = 1
2	26	4070	gcd(4070-26, 7571) = 1
3	677	2964	gcd(2964-677, 7571) = 1
4	4070	2601	gcd(4070-2601, 7571) = 113

d₁=113 d₂=

Demak bizda 7571 = 113*67 ga teng.

Dasturi:
def gcd(a,b):

i = 1
for e in range(1,a*b):
if a%e==0 and b%e==0 :
i = e
return i
def F_function(x,n):
result = x*x+1
if result
return result
else :
return result%n
def pollard(n):
x0 = 2
y0 = 2
print('--------------------------------------')
print('xi '+' yi '+' EKUB(|xi-yi|,n) ')
while True :
x = F_function(x0,n)
y = F_function(F_function(y0,n),n)
print(str(x)+' '+str(y)+' EKUB( |'+str(x)+' - '+str(y)+'|, '+str(n)+' ) = '+str(gcd(abs(x-y),n)))
if gcd(abs(x-y),n)!=1 :
break
x0 = x
y0 = y
pollard(7571)