O’zbekiston respublikasi axborot va kommunikatsion texnologiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

Download 0.7 Mb.
Sana	31.10.2023
Hajmi	0.7 Mb.
	#91910

Bog'liq
1697172460 (1)
7-lab, Maktabgacha yoshdagi bolalarning rivojlanishining o’ziga xos xususiyatlari, bekzod, Bekzod

O’ZBEKISTON RESPUBLIKASI AXBOROT VA KOMMUNIKATSION TEXNOLOGIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Kriptografiya FANIDAN

1 – Amaliy ishi
MAVZU: Modulyar arifmetika. Evklid va kengaytirilgan Evklid algoritmi hamda ularning dasturiy ta‘minotini ishlab chiqish.
BAJARDI: CRY001 GURUH TALABASI
TURSUNOV SARDOR
TOSHKENT 2023
16 –VARIANT
1-topshiriq
o’rinli bo’lganda ni toping ?

#include
using namespace std;
// 1 topshiriq
// 16-variant
int main() {
// b = a mod n = ?
// b = a - n * floor(a / n)
// a = -67 va n = 23 unda b = -67 - 23 * floor(-67 / 23) = -67 - 23 * (-3) =
// = -67 - (- 69) = -67 + 69 = 2
int a = -67, n = 23;
cout << (a % n + n) % n;
}
C++ qoldiqli bo’lish amalga oshirilgan. Buning uchun 2 ta o’zgaruvchi a va n ochilgan.
Ekranga chiqariladi: a sonni qoldiqli bo’ladi n va qoldiqqa n sonini qo’shamiz. Chiqqan javobni n ga qoldiqli bo’lamiz.

2-topshiriq
va berilgan holda d ni toping?

#include

using namespace std;

// 2 topshiriq
// 16-variant
int main() {
// (d * e) mod n = 1 ni qanoatlantiruvchi d ni topish lozim!
// barcha d larni qo`lda o`sib borish tartibida ko`rib chiqamiz.

int n = 41, e = 6;
for(int d = 1; d < n; ++d) {
cout << d << "*" << e << " mod " << n << " = " << d * e % n << endl;
if(d * e % n == 1) {
cout << "Qidirilayotgan d soni " << d << " dir\n";
break;
}
}
}
Edmodn=1 ni yechish uchun quyidagi tenglamani yozsak o’rinli hisoblanadi:
Ed+ny=1 Evklid algoritmi
6d+41y=1
41=6*6+5
6=5*1+1
5=5*1+0
Kengaytrilgan evklid algoritmi:
1=6-5*1
1=6-(41-6*6)
1=7*6-41
Shu ifodadan d=7, y = -1

3-topshiriq
va , - qiymatlar topilsin.

#include
using namespace std;
// 3-topshiriq
// 16-variant
int gcd (int a, int b, int & x, int & y) {
if (a == 0) {
x = 0; y = 1;
cout << "alpha = " << x << ' ' << "betta = " << y << " qoldiq = " << b << '\n';
return b;
}
int x1, y1;
int d = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
cout << "alpha = " << x << ' ' << "betta = " << y << " qoldiq = " << b << '\n';
return d;
}

int main() {

// berilgan a va b sonlari uchun a * alpha + b * betta = 1 diofant tenglamasini ishlash lozim.
int a = 2470, b = 2508, x, y;

cout << "Hisoblash qadamlari:\n";
int gc = gcd(a, b, x, y);
cout << endl;

cout << a << " va " << b << " sonlarining o`zaro ekubi " << gc << " ga teng!\n";
cout << "alpha = " << x << ' ' << "betta = " << y << endl;
}
Ekub evklid algoritmi bo’yicha:
2508=2470*1+38
2470=38*65+0
Ekub=38
2508a+2470b=38
Evklidni kengaytrilgan algoritmi:
38=2508-2470
Bundan a=1 b=-1

4-topshiriq
Qoldiqni hisoblashning effektiv usulidan foydalanib ni hisoblang

#include

using namespace std;

// 4-topshiriq
// 16-variant

int binpow(int a, int b, int n){
int ans = 1;
while(b > 0){
if(b & 1) ans = 1LL * a * ans % n;
a = 1LL * a * a % n;
b >>= 1;
}
return ans;
}

int main() {

// berilgan a va e (a ^ e) mod n ni hisoblang!
int a = 14, n = 73, e = 547;

int ans = binpow(a, e, n);
cout << "a daraja e mod n = " << ans << '\n';
}
Darajani ikkilik songa aylantiramiz.
Bu qoldiqni effektiv usulini hisoblashga kerak
Ans degan o’zgaruvchi ochiladi. While da b noldan kata bo’lsa:
Ans a*ans%n ni o’zlashtiradi.
Yoki a = a*a%n va b>>= 1 amali bajariladi
While dan chiqib ans qaytaradi

Download 0.7 Mb.