Algoritma Prensibi:
Genişletilmiş Öklit Algoritması, yalnızca iki tamsayı a ve m'nin en büyük ortak bölenini ebob(a, m) hesaplamakla kalmaz, aynı zamanda ax + my = gcd(a, m)。
eşitliğini sağlayan x ve y tamsayılarını bulur. Bu, Bézout özdeşliğinin (Bézout denklemi) bir uygulamasıdır.
Algoritma Adımları:
- Öklit Algoritması:Bölme algoritmasını kullanarak ebob(a, m) hesapla, her adımdaki bölüm ve kalanı kaydet.
- Geriye Doğru Yerine Koyma:Son adımdan başlayarak, her kalanı a ve m'nin doğrusal bir kombinasyonu olarak ifade etmek için geriye doğru yerine koy.
- Katsayıları Bulma:Son olarak, ax + my = ebob(a, m) eşitliğini sağlayan x ve y katsayılarını elde et.
Modüler Ters:
ebob(a, m) = 1 olduğunda (yani a ve m aralarında asal), a'nın modül m'ye göre bir çarpımsal tersi vardır ve a-1 mod m olarak gösterilir. Bu durumda x, modüler terstir ve a × x ≡ 1 (mod m)。
eşitliğini sağlar. x negatifse, pozitif bir değere ayarlanması gerekir: x' = x mod m.
Uygulamalar:
- Kriptografi:RSA algoritmasında özel anahtar hesaplamak için modüler ters bulma gerekir.
- Sayı Teorisi Problemleri:ax ≡ b (mod m) şeklindeki doğrusal denkliklerin çözümü.
- Kombinatorik:Modüler Kombinatorik Hesaplama (Lucas Teoremi vb.)
- Rekabetçi Programlama:Bölme işleminden kaynaklanan hassasiyet sorunlarını önlemek için hızlı modüler ters hesaplama
Zaman Karmaşıklığı:
O(log min(a, m)), Öklit Algoritması ile Aynı
Bézout Özdeşliği:
Herhangi a ve m tamsayıları için ax + my = ebob(a, m) olacak şekilde x ve y tamsayıları vardır. Bu x ve y katsayıları, Genişletilmiş Öklit Algoritması kullanılarak verimli bir şekilde hesaplanabilir.