extended euclidean ( uzatılmış öklit veya öklid ) bağlantısı ve algoritması

ö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.

 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.