Genişletilmiş Öklid Algoritması

Matematik / Sayı Teorisi O(log min(a, b)) O(1)

Öklid'i Bézout katsayılarını izleyerek çalıştırır; gcd(a, b) = x·a + y·b ile biter — modüler tersin anahtarı.

q	r	s	t
—	240	1	0
—	46	0	1

abher satırda r = s·a + t·b korunur

1/12

İki satır tohumlanıyor: 240 = 1·a + 0·b ve 46 = 0·a + 1·b — her satır r = s·a + t·b değişmezini korur.

DeğişmezHer satır r = s·a + t·b eşitliğini sağlar; r gcd'ye ulaştığında katsayılar da onunla gelir.

extended-euclidean.c

void extendedGcd(int a, int b) {
    int old_r = a, r = b;
    int old_s = 1, s = 0;     /* coeff of a */
    int old_t = 0, t = 1;     /* coeff of b */
    while (r != 0) {
        int q = old_r / r;
        int tmp;
        tmp = old_r - q*r; old_r = r; r = tmp;
        tmp = old_s - q*s; old_s = s; s = tmp;
        tmp = old_t - q*t; old_t = t; t = tmp;
    }
    printf("gcd = %d = %d*a + %d*b\n",
           old_r, old_s, old_t);
}

Genişletilmiş Öklid Algoritması nasıl çalışır?

Öklid'i, her kalanı x·a + y·b olarak ifade eden iki ek dizi taşıyarak çalıştır. Kalan gcd'ye ulaştığında katsayıları Bézout çiftidir.

Ne zaman kullanılır?

Modüler ters (RSA, hashing), ax + by = c çözümü, Çin Kalan Teoremi.