Guruh talabasi Mirabdullayev Fayzullo 1-amaliy ish

713-21 guruh talabasi Mirabdullayev Fayzullo

1-amaliy ish
Sonning moduli, Evklid algoritmlari va berilgan modul bo’yicha teskari elementni topishga oid misollar berilgan. O‘zingizning tartib raqamingizdagi berilganlarni bajaring va qadamma – qadam izohlang.



Bajarilishi:
1-savol
b=a mod n o`rinli bo`lganda b ni toping.

b=-63mod6

biz bu yerda a>0 bo`lmagunga qadar a ga n ni qo`shib boramiz:
-63+6+6+6+6+6+6+6+6+6+6+6=3
demak, b=3
2-savol
(e*d)mod n = 1. y va n berilgan holda d ni toping.

n=29, e=6

(6d)mod 29=1
Evklidning kengaytirilgan algoritmiga ko`ra:
29=6*4+5 (1)
6=5*1+1
Bundan, 1=6-5*1 ekanligi kelib chiqadi
(1)-tenglikdan 5=29-6*4
1=6-(29-6*4)*1
1=6*5-29
d=6
3-savol
va , - qiymatlar topilsin
A=3760, B=5632

Yechilishi:

A va B sonlarining EKUBini Evklid algoritmi bo`yicha hisoblaymiz
5632=3760*1+1872
3760=1872*2+16
1872=16*117+0
EKUB(5632, 3760)=16


4-savol
Qoldiqni hisoblashning effektiv usulidan foydalanib ni hisoblang
a=82
n=47
e=468

Dastlab e=468 sonini o`nlikdan ikkilik sanoq tizimiga o`tkazib olamiz:

=? ni hisoblaymiz
Qiymatlar quyidagi qoida bo‘yicha hisoblanadi:









Demak,

https://planetcalc.ru/8326/

2- amaliy ish
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.

Topshiriq

1. 
   Tub sonlarni generatsiya qiladigan ( Delpi, Java, C++ va C# dasturlash tizimlaridan biridan foydalangan holda ) dasturiy vosita ishlab chiqilsin.
   
2. 
   Ferma usuli yoki Pollard usuli foydalangan holda N sonini tub ko‘paytuvchilarga ajrating
   

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’adi.

Misol: n=6499
n = p ² – q ²=(p-q)*(p+q);

q	n+ q ^2
1	6499+1=6500
2	6499+4=6503
3	6499+9=6508
4	6499+16=6517
5	6499+25=6524
6	6499+36=6535
7	6499+49=6548
8	6499+64=6563
9	6499+81=6580
10	6499+100=6599
11	6499+121=6620
12	6499+144=6643
13	6499+169=6668
14	6499+196=6695
15	6499+225=6724=82^2

q=15, p=82
n=(82+15)*(82-15)=97*67;