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


Download 99.74 Kb.
bet3/5
Sana08.10.2023
Hajmi99.74 Kb.
#1695298
1   2   3   4   5
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:
, r1= ax1 + b y1;
r2= ax2+ by2;
r 3= ax3+ b y3;


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


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.



Download 99.74 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




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