Uzatılmış Öklit Algoritması (Extended Euclid Algorithm)


Yazan: Şadi Evren ŞEKER

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.

 

Bu Yazıyı Paylaşın


« Diffie-Hellman Ahahtar Değişimi (Key Exchange)   |   Veri Tanımlama Dili (Data Definition Language) »



Yorumlar

Giriş yaparak yorum yazabilirsiniz.

Bu Yazı Hakkında

bilgisayar.kavramlari.com üzerinde şu anda okumakta olduğunuz 'Uzatılmış Öklit Algoritması (Extended Euclid Algorithm)' isimli yazı 20 Mar 2008 tarihinde, saat: 11:49 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 222 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği, Veri Güvenliği(Cryptography) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


Eklenen Son Yazılar
Yapılan Son Yorumlar
Bağlantılar
Kapat
E-posta ile paylaş