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

Multiplikativ teskarilash. Agar tenglik o‘rinli bo‘lsa butun sonlar to‘plamida a va b sonlar o‘zaro teskari sonlar deyiladi.
Modul arifmetikasida arifmetik butun son o‘zaro multplikativ teskarisiga ega bo‘lishi va ega bo‘lmasligi mumkin. Modul bo‘yicha son va uning multiplikativ ko‘paytmasi 1 ga teng bo‘ladi.
Shuni ta’kidlash lozimki agar a sonining modul bo‘yicha teskarisi mavjud bo‘ladi, faqatgina tenglik bajarilsa, yani ular o‘zaro tub bo‘lsa.
Kengaytirilgan Yevklid algoritmi orqali biz butun sonning modul bo‘yicha multiplikativ teskarisini topishimiz mumkin. Buning uchun biz tenglamadagi butun qiymatni modul ga almashtiramiz. Shundan so‘ng tenglama quyidagi ko‘rinishga ega bo‘ladi. . Kengaytirilgan Yevklid algoritmida modul bo‘yicha soniga teskari son faqat shart bajarilgandagina mavjud bo‘ladi. Tenglamada soniga modul bo‘yicha teskari son bu, o‘zgaruvchidir. Bu shuni anglatadiki kengaytirilgan Yevklid algoritmi orqali faqat
Teskari sonni topish algoritmi quyidagicha.

1. 
   Mashg‘ulot. to‘plamda o‘zaro teskari sonlar juftligini aniqlang.
   

Dastlab misol uchun 7 soniga 11 modul bo‘yicha teskari sonni aniqlaymiz. Bu son 8, chunki Xuddi shunga o‘xshash barcha sonlaring teskari juftlarini aniqlaymiz. (1,1); (2,6); 3,4); (5,9); (9,9); (10,10).
2-mashg‘ulot. Modul bo‘yicha teskarilash amalini ixtiyoriy dasturlash tilida dastuini tuzing.
C# dasturlash tilini ishga tushirib, teskari nomli fayl xosil qilamiz.

Asosiy oynaga quyidagi dastur kodini kiritamiz.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Teskari_sonni_topish

{
class Program
{
static void Main(string[] args)
{
// Multipliktiv teskari sonni topish. Muallif Umidjon.15.03.2017
nishon:
Console.WriteLine("Songa multiplikativ teskari sonni topish");
int r1, r2, r, t1, t2, t, q, a, b,n;
Console.Write("sonni kiriting b= ");
b = int.Parse(Console.ReadLine());
Console.Write("modulni kiriting n= ");
n = int.Parse(Console.ReadLine());
////////////////////////////////////////////////////
r1 = n; r2 = b; //initalizatsiya
t1 = 0; t2 = 1;
while (r2 > 0)
{
/////////////////////////////////////////
q = r1 / r2; // r ni aniqlash
r = r1 - q * r2;
r1 = r2;
r2 = r;
/////////////////////////////////////////
t = t1 - t2 * q;
t1 = t2; t2 = t;
}
// tublikka tekshirish
if (r1 == 1)
{
if (t1 >= 0)
{
a = t1;
}
else
{
a = n + t1;
}
Console.WriteLine("Chekli " + n + " maydonda " + b + " soniga teskari son " + a + " ga teng.");
}
else
{
Console.WriteLine("BERILGAN SONGA BERILGAN MODUL BO'YICHA TESKARI SON YO`Q");
}
Console.WriteLine();
goto nishon;
Console.ReadKey();
}
}
}