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



Download 0,58 Mb.
bet2/8
Sana30.04.2022
Hajmi0,58 Mb.
#595358
1   2   3   4   5   6   7   8
Bog'liq
1-6 amaliy ishlar.

b=r1q2+r2, 0 r21,
…………, …………,
rn-2=rn-1 qn+rn, 0 rnn-1,
rn-1 =rnqn+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.

  1. 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.

Download 0,58 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish