T. J. R o’rinli bo’lganda ni toping ?

(e*d)modn=1 e va n berilgan holda d ni toping?


(4*d)mod23=1

Berilgan tenglama (4d ≡ 1 (mod 23)) ni yechish uchun d ni topishimiz kerak. Bu yerda "mod 23" qoldiqlashni ifodalaydi.

Eng avval, 4d ni izolyatsiyalaymiz:

4d ≡ 1 (mod 23)

Endi bizning maqsadimiz 4d ni yalpi o'ng tomonda turib, d ni izolatsiyalashdir. Bu uchun 4 ning 23 ga nisbatan teskari elementini topamiz. To'g'ri teskari elementni topish uchun 4 ni 23 ga nisbatan nisbatan teskarisini topib olishimiz kerak.

Birinchi qadam, teskarisini topamiz.

4 * 6 ≡ 24 ≡ 1 (mod 23)

Bu yerda 6, 4 ning 23 ga nisbatan teskari elementidir. Demak, 4d ≡ 1 (mod 23) tenglamasi quyidagi ko'rinishda yoziladi:

4d ≡ 1 (mod 23)

6 ni o'ng tomon bilan ko'paytiramiz:

4d * 6 ≡ 1 * 6 (mod 23)


24d ≡ 6 (mod 23)

Endi 24d ni 23 ga nisbatan o'ng tomonda izolatsiyalaymiz:

d ≡ 6 (mod 23)

Demak, berilgan tenglama (4d ≡ 1 (mod 23)) uchun d = 6 ga teng

3 va , - qiymatlar topilsin.

EKUB(4386,6273)

Yevklid algoritmi qadamlariga muvofiq:

6273=4386*1+1887 ya’ni

4386=1887*2+612 ya’ni

1887=612*3+51 ya’ni

612=51*12+0 ya’ni

demak,

soni 4386 va 6273 sonlarining -deb e’lon kilinadi, ya’ni
.
Kengaytirilgan Evklid algoritmiga ko‘ra:

=?, =? topaylik:
yuqorida keltirilgan ifodani quyidagicha yozib olamiz:

51=1887-612*3

612=4386-1887*2

1887=6273-4386*1

yoki :
51=1887-612*3=1887-3*(4386-1887*2)=7*(6273-4386*1)-3*4386=

=7*6273-10*4386 => demak, =-10; = 7