1-amaliy mashg’ulot Mavzu: Kriptografiyaning matematik asosi. Ishning maqsadi

b=r₁q₂+r₂, 0 r₂₁,
…………, …………,
r_n-2=r_n-1 q_n+r_n, 0 r_nn-1,
r_n-1 =r_nq_n+1.
Ishning bajarilish tartibi. Quyida Yevklid algoritmi blok sxemasini ko‘rib chiqamiz
Jarayon va algoritm quyidagicha.
Quyidagi misolni ko‘rib o‘tamiz.

1. 
   1-topshiriq 36 va 10 sonlarini EKUB ini hisoblang.
   

Yevklid algoritmidan foydalanib quyi dagi jadvalda masalani yechamiz.

R1	R2	q	r
36	10	3	6
10	6	1	4
6	4	1	2
4	2	2	0
2	0	-	-

Jadvaldan ma’lumki 36 va 10 sonlarini EKUBI 2.

2. 
   39 va 17 sonlarini EKUB ini hisoblang.
   

Yevklid algoritmidan foydalanib quyi dagi jadvalda masalani yechamiz

R1	R2	q	r
39	17	2	5
17	5	3	2
5	2	2	1
2	1	2	0
1	0	-	-

Jadvaldam ma’lumki 39 va 17 sonlarining EKUBI. 1. Demak ular o‘zaro tub sonlar.

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Evklid_algoritmi { class Program { static void Main(string[] args) { // a va b sonlarini EKUBini topish. EVKLID algoritmi. Console.Write("a="); int a = int.Parse(Console.ReadLine()); Console.Write("b="); int b = int.Parse(Console.ReadLine()); int k= gcd(a, b); Console.Write("EKUB({0},{1}= {2}",a,b,k); Console.ReadKey(); } static int gcd(int r1, int r2) { int q, r; while (r2 > 0) { q = r1 / r2; // qoldiqni aniqlash r = r1 - q * r2;// yoki r=r1%r2; r1 = r2; r2 = r; } return r1; }}}

Endi yuqorilagi misolni dasturda sinab ko‘ramiz.

Hisobot tarkibi
Hisobot quyidagi ma’lumotlardan tarkib topgan bo‘lishi lozim:
Nazariy qismda keltirilgan algoritmning dasturiy ta’minotidan foydalanish jarayonidagi olingan rasmlari va ularga izoh.
Yaratilgan dasturiy ta’minotning dasturiy kodi.
Nazorat Savollari
Sonning EKUBi tushunchasi
Yevklid algoritmi
Qoldiqli bo‘lish
2-amaliy mashg’ulot.
Mavzu: Kengaytirilgan Yevklid algoritmi.
Ishning maqsadi: Kengaytirilgan algoritmi bilan ishlash va chiziqli diofant tenglamalarini kengaytirilgan Yevklid algoritmi yordamida umumiy va xususiy yechimlarini topishni o‘rganish.
Nazariy qism. Agar arifmetik butun sonlar ustida tenglik o‘rinli bo‘lsa soni sonini bo‘luvchisi deyiladi va kabi belgilanadi. sonining bo‘luvchilari deganda sonni bo‘luvchi noldan farqli barcha sonlarga aytiladi.

1-teorema. Butun a va b sonlari o‘zaro tub bo‘ladi, qachonki shunday butun u va v sonlari topilsaki, ular uchun au+bv=1 tenglik o‘rinli bo‘lsa.
Bu keltirilgan teoremani quyidagicha ham ifodalash mumkin: butun a va b sonlari o‘zaro tub bo‘lishi uchun, butun bo‘lgan s va t sonlari topilib, ular uchun as+bt=1 tenglikning bajarilishi zarur va yetarli.
Kengaytirilgan Yevklid algoritmida bir paytning o‘zida EKUB(a,b) ni hamda s va t o‘zgaruvchilarni hisolash imkoni mavjud. Algoritm oddiy Yevklid algoritmiga o‘xshash va uchta o‘zgaruvchilardan foyalanadi.
Quyidagi rasmda jarayon aks ettirilgan.

va o‘zgaruvchilar, oddiy Yevklid algoritmidan topiladi. O‘z navbatida qolgan o‘zgaruvchilarga boshlang‘ich qiymat beriladi.
Kengaytirilgan Yevklid algoritmini quyidagicha realizatsiya qilish mumkin.

O‘zaro tub sonlarni topish va ikki o‘zgaruvchili chiziqli diofant tenglamalarni yechish uchun kengaytirilgan Yevklid algoritmilan foydalaniladi.