Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti Kriptografiya 1

Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Kriptografiya 1

5-Amaliy ish

Mavzu:Evklid va kengaytirilgan Evklid algoritmi.


Bajardi:070-20 - guruh talabalari
Salimova N.
Samadova D.
Kanalbekov U.
Turdiyev B.
Karimberdiyev Sh.
Tekshirdi: Mardiyev U. R.

Tashkent – 2023

5 – Amaliy ish
Mavzu: Evfklid va kengaytirilgan Evfklid algoritimi.
Evklid algoritmi ikki butun sonning eng katta umumiy boʻluvchisini (GCD) topish usulidir. Buni birinchi marta qadimgi yunon matematigi Evklid o'zining "Elementlar" kitobida tasvirlab bergan.
Evklid algoritmining asosiy g'oyasi raqamlardan biri nolga aylanguncha kichik sonni katta raqamdan qayta-qayta ayirishdir. GCD keyin qolgan nolga teng bo'lmagan raqamdir. Bu algoritm batafsilroq:
1. a va b GCD ni topmoqchi bo'lgan ikkita butun son bo'lsin.
2. Katta sonni kichik songa bo'ling va r qoldiq bo'lsin.
3. Agar r nolga teng bo'lsa, u holda GCD kichikroq sondir.
4. Agar r nolga teng bo'lmasa, u holda b o'rniga a, a ni r bilan almashtiring va 2-bosqichga qayting.
Bu jarayon r nolga aylanmaguncha takrorlanishi mumkin, bunda GCD a yoki b ning nolga teng bo'lmagan oxirgi qiymati hisoblanadi.
Algoritmni tasvirlash uchun quyidagi misol:
84 va 18 GCD ni Evklid algoritmidan foydalanib topamiz.
1. a = 84, b = 18
2. 84 ni 18 ga bo'ling: 84 = 4 * 18 + 12. Bu erda 12 - qoldiq.
3. a = 18, b = 12
4. 18 ni 12 ga bo'ling: 18 = 1 * 12 + 6. Bu erda 6 - qoldiq.
5. a = 12, b = 6
6. 12 ni 6 ga bo'ling: 12 = 2 * 6 + 0. Bu erda 0 qoldiq.
7. Qolgan nolga teng bo'lganligi sababli, GCD a yoki b ning nolga teng bo'lmagan oxirgi qiymati bo'lib, u 6 ga teng.
Shuning uchun 84 va 18 GCD 6 ga teng. Evklid algoritmi ikkita butun sonning GCD ni topishning juda samarali usuli bo'lib, u sonlar nazariyasi, kriptografiya va informatika sohasida ko'plab ilovalarga ega.
Evfklid algoritimining dasturiy tuzilishi

using System;

class Program
{
static void Main()
{
Console.Write("a: ");
int a = int.Parse(Console.ReadLine());
Console.Write("b: ");
int b = int.Parse(Console.ReadLine());

int gcd = EvfklidAlgoritm(a, b);

Console.WriteLine($"GCD {a} va {b} dan {gcd} teng deb topildi");
}

static int EvfklidAlgoritm(int a, int b)

{
while (b != 0)
{
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}
Kiruvchi qiymat: a = 84, b = 18
Natija : GCD 84 va 18 dan 6 teng deb topildi

Kengaytirilgan Evfklid algoritimi.

Albatta! Kengaytirilgan Evklid algoritmi Evklid algoritmining kengaytmasi boʻlib, u nafaqat ikkita butun sonning eng katta umumiy boʻluvchisini (GCD) topadi, balki GCD ni asl ikki butun sonning chiziqli birikmasi sifatida ifodalash uchun ishlatilishi mumkin boʻlgan bir juft koeffitsientni ham topadi.
Algoritm ikkita manfiy bo'lmagan a va b butun sonlardan boshlanadi va a ni b ga bo'lganda r1 qoldig'ini topish orqali davom etadi. Agar r1 nolga teng bo'lsa, u holda a va b ning GCD oddiygina b bo'ladi. Aks holda, algoritm rekursiv ravishda b va r1 ga qo'llaniladi va nolning qoldig'i olinmaguncha davom etadi.
Shu bilan birga, algoritm tenglamani qanoatlantiradigan s va t juft koeffitsientlarini ham hisoblab chiqadi:
sa + tb = gcd(a, b)
s va t koeffitsientlari GCD ni a va b ning chiziqli birikmasi sifatida ifodalash uchun ishlatilishi mumkin.
Kengaytirilgan Evklid algoritmini tasvirlash uchun quyidagi misol:
Kengaytirilgan Evklid algoritmidan foydalanib, 60 va 48 GCD ni topamiz. Biz 60 ni 48 ga bo'lish va qolganni topish bilan boshlaymiz:
60 = 48 * 1 + 12
Qolganlari 12 ga teng, shuning uchun biz algoritmni 48 va 12 ga qo'llaymiz:
48 = 12 * 4 + 0
Qolgan nolga teng bo'lgani uchun biz to'xtab, 60 va 48 GCD 12 ga teng degan xulosaga kelamiz.
Endi s va t koeffitsientlarini topish uchun orqaga qarab ishlay olamiz. Biz tenglamadan boshlaymiz:
sa + tb = gcd(a, b)
Va biz topgan qiymatlarni almashtiring:
12 = 60 * s + 48 * t
Ikkala tomonni 12 ga bo'lish orqali bu tenglamani soddalashtirishimiz mumkin:
1 = 5s + 4t
Endi bu tenglamani qanoatlantiradigan s va t qiymatlarini topishimiz kerak. Buning bir usuli - algoritmni qayta ishlatish, lekin bu safar oxirgi bosqichdan orqaga qarab ishlash:
1 = 5s + 4t
1 = 5(1) + 4(0) (chunki 5 va 4 oʻzaro tubdir)
0 = 5(0) + 4(1) (oldingi tenglamaning 4 barobarini 1 karra o'zidan ayirish)
1 = 5(1) + 4(-1) (oldingi tenglamaning 4 karrasini 5 karra o'zidan ayirish)
Shunday qilib, biz s = 1 va t = -1 tenglamani qondirishini aniqladik va biz 60 va 48 ning GCD ni quyidagicha ifodalashimiz mumkin:
12 = 60 * 1 + 48 * (-1)
Kengaytirilgan Evfklid Dastur qodi.
using System;
class Program
{
static void Main()
{
Console.Write("a: ");
int a = int.Parse(Console.ReadLine());
Console.Write("b: ");
int b = int.Parse(Console.ReadLine());

int gcd = ExtendedEuclideanAlgorithm(a, b, out int x, out int y);

Console.WriteLine($"GCD {a} va {b} dan {gcd} teng deb topildi");

Console.WriteLine($"{gcd} = {a} * {x} + {b} * {y}");
}
static int ExtendedEuclideanAlgorithm(int a, int b, out int x, out int y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int gcd = ExtendedEuclideanAlgorithm(b, a % b, out int x1, out int y1);
x = y1;
y = x1 - (a / b) * y1;
return gcd;
}
}
Kirib keluvchi qiymat: a = 60 b = 48
Natija : GCD 60 va 48 dan 12 teng deb topildi
12 = 60 * 1 + 48 * -1