1- amaliy ish Mavzu: Modulyar arifmetika. Evklid va kengaytirilgan Evklid algoritmi hamda ularning dasturiy ta‘minotini ishlab chiqish. Ishdan maqsad

Kengaytirlgan Evklid algoritmi
Kengaytirlgan Evklid algoritmi RSA kriptotizimi ochiq kaliti -ni topishda taqqoslama tenglamaga duch kelinib, uni yechish bevosita , tenglama butun yechimlarini topish masalasiga ekvivalent hamda bu algoritmga ko‘ra berilgan –soniga bo‘yicha teskari elementni topish imkonini beradi. Shuning uchun ham bu algoritm ishlash prinsiplarini keltirib o‘tamiz.
Teorema. Aytaylik, va natural sonlar, bo‘lsin. U holda shunday va butun sonlar topiladiki

tenglik o‘rinli bo‘ladi.
Demak, bu algoritm nafaqat ikkita natural sonning –ni, balki yoyilmadagi va koeffisentlarni ham topish imkonini berar ekan.
Shunisi bilan ham aslida Evklid algoritmidan farqlanadi.
Kengaytirilgan Evklid algoritmiga muvofiq topiladigan va butun sonlar, quyidagi Diafant tenglamasi

butun yechimlari hisoblanadi. Bu esa esa bizga RSA algoritmi ochiq va maxfiy kalitlarini topish imkonini yaratadi. Shu sababli bu algoritm ishlash qadamlari bilan yaqindan tanishib chiqamiz va misollarga qo‘llab ko‘rsatamiz.
Faraz qilaylik, va sonlarning - ni topishda quyidagi ketma-ketlik qaralayotgan bo‘lsin:
, r₁= ax₁ + b y_1;
r₂= ax₂+ by₂;
r ₃= ax₃+ b y₃;


………………. ………………..


Biz, bu yerda
va
sonlarini topishimiz kerak. Bu sonlar quyidagi formula yordamida topiladi:
va
bu yerda

Kerakli maьlumotlarni quyidagi jadval orqali berish mumkin

qoldiqlar	bo‘luvchi

Jadvalda keltirilgan oxirgi ustundagi ikki qiymat biz izlayotgan alfa va betta koeffisentlardir, yaьni teng bo‘ladi.