öklit methodunun bir ileri versiyonu olarak düşünülebilir. Örneğin öklit bağlantısında:
a − qb = a mod b bağlantısı öne atılmıştır, burada q katsayısı bağlantı
dengesini bozmaz (Ancak, gcd(0, b) = b; olmalı ve gcd(a, b) = gcd(b, a
− qb) olmalıdır)

uzatılmış öklit bağlantısı işlemi için detaylı algoritma açıklamasına bu bağlantıdan erişebilirsiniz ve detayları aşağıda verilmiştir:

Bu yöntemin amacı berlirli bir tabana(modulus) göre verilen sayının tersini bulmaktır. Yani basitçe de = 1 mod p denklemini bilinen bir d ve p sayısı için çözmektir. Başka bir ifadeyle bir sayının bir modda hangi sayıyla çarpılınca 1 sonucunu verdiğini bulmaktır.

Buna göre algoritmada tersi alınacak olan sayı d ve taban değeri olan p biliniyor olacak ancak e sayısı (yani d sayısının tersi olan sayı) aranacaktır. Bu sayı aşağıdaki şekilde de ifade edilebilir:

d-1 = e mod p

Yukarıda d sayısının tersi olarak ifade edilen e sayısı için aşağıdaki algoritma adımları izlenebilir:

  1. (X1, X2, X3) <- (1 ,0 ,p) sayıları konulur
  2. (Y1, Y2, Y3) <- (0, 1, d) sayıları konulur
  3. Şayet Y3 değeri 0 ise tersi yoktu hükmüne varılıp algoritma sonu erdirilir.
  4. Şayet Y3 değeri 1 ise aranan ters değer Y2 değeridir ve dY2 ≡ 1 mod p yadad-1 = Y2 mod p , sonucuna varılarak algoritma sonlandırılır
  5. Q değeri hesaplanır : Q= |_ X3 / Y3 _|
  6. (T1, T2, T3) <- ( X1 – QY1, X2 – QY2, X3 – QY3) değerleri hesaplanarak yerleştirilir.
  7. (X1, X2, X3) <- (Y1, Y2, Y3)
  8. (Y1, Y2, Y3) <- (X1, X2, X3)
  9. bu adımdan 2. adıma geri dönülür.

Yukarıda algoritması verilmiş olan uzatılmış öklit metodunda çıkan sonuç yani verilmiş olan d ve p değerleri için bulunan e ( algoritmadaki Y2 ) değeri sonuçta aşağıdaki yorumlara izin verir:

de ≡ 1 mod p

ep ≡ 1 mod d

dolayısıyla hem d hem de p tabanına göre sayının tersi bulunmuş olur. Bu işlem aşağıdaki tabloda bir örnek ile anlatılmıştır:

Örneğin 97 ve 127 sayılarına göre ters sayıyı bulmaya çalışalım. Bu durum basitçe 97x = 1 mod 127 olan x sayısını bulmak olarak yorumlanabilir.

Q

X1

X2

X3

Y1

Y2

Y3

T1

T2

T3

1

1

0

127

0

1

97

1

-1

30

3

0

1

97

1

-1

30

-3

4

7

4

1

-1

30

-3

4

7

13

-17

2

3

-3

4

7

13

-17

2

-52

55

1

 

13

-17

2

-52

55

1

 

 

 

 Yukarıdaki örnekte Y3 değeri 1 olunca durulmuş ve sayının tersi olarak Y2 hücresinde yazan değer yanı 55 bulunmuştur. Bu işlemden sonra 55.127=1 mod 97 veya 55.97 = 1 mod 127 yorumu yapılabilir.

Yorumlar

  1. Ali Tartan

    Bilgi: Algoritma aslında verilen d ve p değerleri için px + ed = gcd(d, p) işleminin sonucunu arar (yani x ve e değerlerini bulmaya çalışır). d ve p aralarında asal olmalıdır ki px + ed = 1 olsun, böylece ed = 1 mod p işleminin sonucu bulanabilsin.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


5 × iki =