|
Muhammad al-xorazmiy nomidagi toshkent axborot texnalogiyalari universiteti
|
| Sana | 15.12.2023 | | Hajmi | 115.79 Kb. | | #119227 |
Bog'liq Azotli oʻgʻitlar - Vikipediya, 164041196515690415, Tasavvur qiling (2), TFNA. Must top3. BT2sirtqi Davlatova S (1), Ðоддий Ñ
иÑоб-fayllar.org, Islom karimov nomidagi toshkent davlat texnika universiteti oziq, portal.guldu.uz-AGROKIMYOVIY TEKSHIRISH USULLARI, Tahlilningfizika-kimyoviyusullarioquvqollanmagrif, 11-15, xumoyunxon, 2.15.-Biofizika-pediatriya-ishi-1-kurs, 81545 5-mavzu, 3-илова, 27amaliy
O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALARI VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNALOGIYALARI
UNIVERSITETI
KRIPTOGRAFIYA 1 fanidan
6-AMALIY ISHI
Bajardi: CRY002-3-guruh talabasi
Sag’dillayev Alibek
Tekshirdi : Mardiev U.R
Toshkent 2023
6-amaliy ish
Mavzu : Faktorizatsiyalash algoritmlari va ularning dasturiy ta‘minotni
ishlab chiqish.
Ishdan maqsad: Faktorlash muammosini bartaraf etish chora tadbirlari to’g’risida nazariy va amaliy ko‘nikmalarga ega bo‘lish.
Variant-16.
1.FERMA USULI.
N=5561
N=a2-b2 // N tub sonini 2ta no’malum sonlarning kvadradlari ayirmasi deb qabul qilamz.
Ferma usulining mohiyati shundan iboratki, N sonI biror sonning to‘la kvadratidan iborat bolganida topa olamiz.
N+b2=a2
5561+b2=a2
5561+b2=752 // bu yerda 5561 dan katta bolgan sonning kvadratiga keltirish uchun b ga nechi qiymat tanlashni korib chiqamiz.
B ning orniga 1 dan boshlab son qiymati berishni boshlaymiz.
b
|
N+b2
|
1
|
5561+12=5562
|
2
|
5561+22=5565
|
3
|
5561+32=5570
|
4
|
5561+42=5577
|
5
|
5561+52=5586
|
6
|
5561+62=5597
|
7
|
5561+72=5610
|
8
|
5561+82=5625=752
|
Demak b=8 qadamida o’rinli bo’ldi.
5561+82=752
5561=752-82
5561=(75-8)*(75+8)
5561=67*83
Demak 5561 soni 2ta a=67 va b=83 tub sonlarining ko’paytmasi.
2.POLLARD USULI.
N=5561
𝐹(𝑥) = (𝑥2 + 1)𝑚𝑜𝑑5561 bo’yicha
𝑛 = 5561, 𝐹(𝑥) = (𝑥 2 + 1)𝑚𝑜𝑑𝑛, 𝑥0 = 𝑦0 = 2
|
i
|
𝑥i = 𝐹(𝑥i−1)
|
𝑦𝑖 = 𝐹(𝐹(𝑥i−1 ))
|
𝐸𝐾𝑈𝐵(|𝑥i – 𝑦i |, 5561)
|
1
|
5
|
26
|
(21:5561)=1
|
2
|
26
|
2328
|
(2302:5561)=1
|
3
|
677
|
3171
|
(2494:5561)=1
|
4
|
2328
|
954
|
(1374:5561)=1
|
5
|
3171
|
3674
|
(503:5561)=1
|
6
|
954
|
1730
|
(776:5561)=1
|
7
|
3674
|
1083
|
(2591:5561)=1
|
8
|
1730
|
5080
|
(3350:5561)=67
|
𝑥0 = 𝑦0 = 2 sonidan boshlab 𝑥i = 𝐹(𝑥i−1) va 𝑦𝑖 = 𝐹(𝐹(𝑥i−1 )) funksiyalarni hisoblab jadvalni to’ldirdik.Shunda 8- qadamida d1=67 chiqdi.
d2=N/d1=5561/67=83
2ta tub ko’paytuvchi ham chiqdi: d1=67 va d2=83.
Ilova.
#
import math
def isprime(n):
n = 9
flag = 0
if n > 1:
for k in range(2, int(math.sqrt(n)) + 1):
if n % k == 0:
flag = 1
break
if flag == 0:
return True
else:
return False
else:
return False
def pollardPMO(n):
a = 2
i = 2
while True:
a = (a**i) % n
d = math.gcd((a - 1), n)
if d > 1:
return d
break
i += 1
n = 5561
num = n
res = []
while True:
d = pollardPMO(num)
res.append(d)
r = int(num / d)
if isprime(r):
res.append(r)
break
else:
num = r
print("Factors of the number:", n, "are", *res)
Nazariy savollar.
1."Faktorlash muammosi" deb aytilganida, umumiy ravishda, bir muammoga yoki muddati cheksiz o'zgaruvchan jarayonga olib keladigan bir nechta omillar yoki sabablarga istinodan kelib chiqqan muammolar yoki vaziyatlar ma'nosini anglatish mumkin. Bu muammo yoki vaziyatlar, bir tizim, jarayon, tashkilot, yoki boshqa bir narsa tomonidan amalga oshirilgan o'zgarishlar yoki faktorlar bilan bog'liq bo'lishi mumkin.
Faktorlash muammosi bir nechta turlarda bo'lishi mumkin. Masalan, biz "faktorlash muammosi" deyishimizda, bir masalaning o'zgarishlarga, yanada kengayishlarga yoki boshqa o'zgaruvchanlarga qanday ta'sir qilishi haqida gaplashishimiz mumkin. Bu o'zgaruvchanlar, moliyaviy, iqtisodiy, ijtimoiy, siyosiy, tabiiy, texnologik yoki boshqa sohalardagi faktorlar bo'lishi mumkin.
2. Pollard usuli, sonlarning faktorlash muammosini hal qilish uchun ishlatiladigan bir algoritm hisoblanadi. Bu usul, asosan katta sonlarni, ya'ni ko'p darajadagi sonlarni, ikki yoki undan ko'p kasrlar va paytlar orqali yengillik bilan faktorlarga bo'lishga imkon beradi. Pollard usuli, sonlarni faktorlarga bo'lish uchun bir nechta yo'nalishlarda ishlatilishi mumkin, masalan, Pollard rho usuli, Pollard p-1 usuli, Pollard kanguru usuli kabi. Har bir usul, o'zining xususiyatlari va chegaralari bilan ajralib turadi, lekin ulardan foydalanish orqali katta sonlarni faktorlarga bo'lish jarayonini tez va samarali tarzda amalga oshirish mumkin.
Pollard usuli, kriptografiyada, xususan, e'tiborli sonlarni (masalan, asosiy sonlarni) faktorlarga bo'lish va shuningdek, katta sonlarni faktorlash uchun ham amalga oshiriladi.
|
| |
