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

Chiziqli diofant tenglamalar bu ikkki o‘zgaruvchilik ko‘rinishidagi tenglamalarga aytiladi.
Bizdan berilgan tenglasani yechish uchun x,y o‘zgaruvchilarni topish talab etiladi. Ushbu tipdagi tenglamalar bitta yechimni qabul qilmaydi. Shuning uchun ularda umumiy va xususiy yechimlar mavjud.
Agar berilgan bo‘lib, tenglik o‘rinli bo‘lsa, tenglama yechimga ega bo‘lmaydi. Agar tenglik bajarilsa, tenglama cheksiz ko‘p yechimga ega bo‘ladi. Ushbu yechimlardan biri xususiy, qolganlari umumiy yechimlar deyiladi.
X ususiy yechimlar:
Xususiy yechim topilgandan so‘ng umumiy yechimni topish mumkin.
Ishning bajarilish tartibi.
1-mashg‘ulot. Butun a=161 va b=28 sonlari berilgan. Kengaytirilgan Yevklid algoritmidan foydalanib EKUB(a,b) va s,t qiymatlarni aniqlang.
Ushbu masalani quyidagi jadvalda algoritm yordamida yechish ketma-ketligi berilgan.

Quyidagi natijalarga ega bo‘lamiz. EKUB(161,28)=7, s=-1, t=6.
2-mashg‘ulot. tenglamaning umumiy va xususiy yechimlarini toping.
Dastlab Yevklid algoritmi yordamida ni xisoblaymiz. 7 soni 35 ga bo‘linganligi uchun, tenglama cheksiz yechimga ega bo‘ladi. Tenglamani ikkala tomonini 7 ga bo‘lamiz va tenglamani hosil qilamiz. tenglamani Yevklid algoritmi yechib, s=1, t=-1 qiymatlarni olamiz.
Formuladan foydalaib, xususiy yechimlarini topamiz. ;
formula yordamida tenglamaning umumiy yechimlarini topamiz. , k=1, 2…
3-mashg‘ulot. Kengaytirilgan Yevklid algoritmi. Chiziqli diofand tenglamalarni yechishning C# dasturlash tilida algoritmi.
C# dasturlash tilini ishga tushirib, extendet_evklid nomli fayl hosil qilamiz. Dastur kodini yozamiz va realizatsiya qilib, kengaytirilgan Yevklid algoritmi va chiziqli diofant tenglamasini yechish jarayonini tekshiramiz.
Dasturning kirish qismi

Asosiy va ishchi oyna.

Asosiy ishchi oynaga quyidagi kodni kiritamiz.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace kENGEvklid

{
class Program
{
static void Main(string[] args)
{// kengaytirilgan Yevklid aloritm.08.03.2017
int a,b,r1, r2, t1, t2, r, s, t, q, s1, s2;
//sxa+txb=EKUB(a,b); ni yechish algoritmi.
Console.WriteLine("ax+by=EKUB(a,b) tenglamani yechish uchun keggaytirilgan\n yevklid algortimi.");
Console.Write("a= ");
a = int.Parse(Console.ReadLine());
Console.Write("b= ");
b = int.Parse(Console.ReadLine());
r1 = a; r2 = b;
s1 = 1; s2 = 0;
t1 = 0; t2 = 1;
while (r2>0)
{
q = r1 / r2;
r = r1 - q * r2; r1 = r2; r2 = r;
s = s1 - q * s2; s1 = s2; s2 = s;
t = t1 - q * t2; t1 = t2; t2 = t;
}
Console.WriteLine("EKUB(" + a + "," + b + ")= " + r1 + " s=" + s1 + " t=" + t1);
Console.ReadKey(); }}}

Yuqoridagiga o‘xshash chiziqli diofant tenglamani dasturini tuzamiz. Kodi quyidagicha.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DIOFANT_TENGLAMA

{
class Program
{
public int EKUB(int a, int b)
{
int r1, r2, r, q;
r1 = a; r2 = b;
while (r2 > 0)
{
q = r1 / r2;
r = r1 - q * r2;
r1 = r2;
r2 = r;
}
return r1;
}
public int Yevklid(int a1, int b1)
{
int q, r1, r2, s, s1, s2, r;
r1 = a1; r2 = b1;
s1 = 1; s2 = 0;
while (r2 > 0)
{
q = r1 / r2;
r = r1 - q * r2;
r1 = r2; r2 = r;
s = s1 - q * s2;
s1 = s2; s2 = s;
}
return s1;
}
public int Yevklids(int a2, int b2)
{
int r, r1, r2, t, t1, t2, q;
r1 = a2; r2 = b2;
t1 = 0; t2 = 1;
while (r2 > 0)
{
q = r1 / r2;
r = r1 - q * r2;
r1 = r2; r2 = r;
t = t1 - q * t2;
t1 = t2;
t2 = t;
}
return t1;
}
static void Main(string[] args)
{
Console.WriteLine("sxa+txb=c chiziqli diofant tenglamani yechish!");
Console.Write("a= ");
int a = int.Parse(Console.ReadLine());
Console.Write("b= ");
int b = int.Parse(Console.ReadLine());
Console.Write("c= ");
int c = int.Parse(Console.ReadLine());
int d = new Program().EKUB(a, b);
Console.WriteLine("d= " + d);
if (c % d != 0)
{
Console.WriteLine("chiziqli diofant tenglama yechimga ega emas!");
}
else
{
int a3=a/d;
int b3=b/d;
int c1=c/d;
// a1s+b1t=1 chiziqli diofant tenglamani yechamiz.

int s=new Program().Yevklid(a3,b3);

int t=new Program().Yevklids(a3,b3);
Console.WriteLine("s= {0}, t= {1}", s,t);
// xususiy yechimlarni aniqlash.

int x0 = (c / d) * s; int y0 = (c / d) * t;

Console.WriteLine("Tenglamaning xususiy yechimlari xo={0} ga, y0= {1} ga teng", x0, y0);
Console.WriteLine("umumiy yechimlar uchun butun k sonini kiriting");
Console.Write("k= ");
int k = int.Parse(Console.ReadLine());
for (int i = 0; i <= k; i++)
{
int x = x0 + i * (b / d);
int y = y0 - i * (a / d);
Console.WriteLine("x["+i+"] = "+x+" y["+i+"] = "+y+" ga teng");
}
}
Console.ReadKey();
}
}
}