47
Izoh.
Kriptografiyada modul sifatida (ya’ni, bo’luvchi) faqat tub sonlardan
foydalanish talab etiladi. Ya’ni,
amodn
tenglikdagi
n
har doim tub bo’lishi talab
etiladi.
Misol
tariqasida, 3 sonining 7 maydondagi teskarisini topish talab etilsin.
Ya’ni,
𝑥𝑥
ni topish talab etilsin:
3
−1
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡ 𝑥𝑥
. Yuqoridagi tenglik
(3
∗ 𝑥𝑥
)
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
1
dan foydalanib,
𝑥𝑥
ning o’rniga son qo’yib natijani hisoblash mumkin. Lekin
ushbu
jarayon ko’p vaqt talab etadi (ayniqsa katta sonlarda juda ham ko’p vaqt talab etiladi).
Ushbu muammoni yechishning ko’plab usullari mavjud bo’lib, quyida
ulardan biri bo’lgan qoldiqlar to’g’risidagi
Yevklidning kengaytirilgan algoritmi
dan
foydalanib yechish usuli keltirilgan.
Kengaytirlgan Yevklid algoritmi.
Kengaytirlgan Yevklid algoritmi RSA
kriptotizimi ochiq kaliti «
ye
» - ni
topishda
𝑑𝑑 ∗ 𝑒𝑒
≡
1(
𝑆𝑆𝑒𝑒𝑑𝑑
ϕ
(
𝑛𝑛
))
tenglamaga duch
kelinib, uni yechish bevosita
𝑎𝑎𝑥𝑥
+
𝑎𝑎𝑦𝑦
=
𝑑𝑑
,
𝑑𝑑
= EKUB(
𝑎𝑎
,
𝑎𝑎
)
tenglamaning butun
yechimlarini topish masalasiga ekvivalent hamda bu algoritmga ko’ra berilgan
a
–
soniga m
𝑒𝑒𝑑𝑑𝑛𝑛
bo’yicha teskari elementni topish imkonini beradi. Shuning
uchun
ham bu algoritm ishlash prinsiplarini keltirish muhim.
Download
