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();
        }

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Güzel soru, şimdi karmaşıklık hesabı için en kötü durum analizi (worst case analysis) yapılması gerekir. Uzatılmış öklit hesaplaması aslında bir ortak böllenlerin en büyüğü hesaplamasıdır (greatest common divisor) ve bu konuda yapılan çalışmalar göstermiştir ki bu algoritma için en kötü durum, 10 tabanında sayıların küçük olanının hane sayısının 5 katından fazla olamaz. Örneğin sayılarımız 12345678 ve 1234 ise küçük olan sayı 4 haneli olduğu için en fazla 4 x 5 = 20 adımda hesaplanır diyeibliriz (elbette daha hızlı da hesaplanabilir ancak en kötü durum analizinde en kötü durum ele alınır).
    Bu durumda hane sayısı (digit) logaritmik bir değer olacağı için karmaşıklık:
    5log10(asgari(X3 , Y3))
    yani log n cinsinden çıkacaktır diyebiliriz.

    Bunun ispatı fibonacci sayılarına dayanıyor ve herhangi bir fibonacci sayısını hesaplamak için gereken karmaşıklık iteratif olarak hesaplanıyor. Aslında yazıya bu hesaplamayı vakit bulabilirsem ekleyeyim. Ancak acil olarak bu bilgiye ihtiyacınız varsa Gabriel Lame tarafından yapılan ispatı inceleyebilirsiniz.

  2. Halit

    Algoritmanın 8.sırasında yazdığınız (Y1, Y2, Y3) <- (X1, X2, X3) satırları (Y1, Y2, Y3) <- (T1, T2, T3) olması gerekiyor.Siz de zaten yazdığınız kod da bu şekilde yapmışssınız ancak algoritma kısmında bir hata olmuş.Diğer yazınızda da aynı hata mevcut.İyi çalışmalar.

Bir cevap yazın

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