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.

Kodlaması

Yukarıda anlatılan algoritmanın C++ dilindeki kodlaması aşağıda verilmiştir:

#include 
#include 
int main(){
            int f,d;
			printf("Sayilari giriniz");
			scanf("%d %d",&f,&d);

            int x1, x2, x3, y1, y2, y3;
            x1 = 1; x2 = 0; x3 = f; //p
            y1 = 0; y2 = 1; y3 = d; //d

            printf("QtX1tX2tX3tY1tY2tY3tT1tT2tT3n");

            int q = 0, i = 1;
            int t1 = 0, t2 = 0, t3 = 0;
            do
            {
                if (i == 1)
                {
                    q = x3 / y3;
                    t1 = x1 - (q * y1);
                    t2 = x2 - (q * y2);
                    t3 = x3 - (q * y3);
                }
                else
                {
                    x1 = y1; x2 = y2; x3 = y3;
                    y1 = t1; y2 = t2; y3 = t3;
                    q = x3 / y3;
                    t1 = x1 - (q * y1);
                    t2 = x2 - (q * y2);
                    t3 = x3 - (q * y3);
                }
                i++;
                printf("%dt%dt%dt%dt%dt%dt%dt%dt%dn",q , x1 , x2 , x3 , y1 , y2 , y3 , t1 , t2 , t3);

                if (y3 == 0)
                {
                    break;
                }

            } while (y3 != 1);
           
            if (y3 == 0)
            {
                printf("Sayinin tersi yoktur!!!!");
            }
            else
            {
                printf("nSayinin tersi : %d" , y2);
            }
	getch();
        }