Modüler Çarpımsal Ters Hesaplayıcı

Hesaplamaya Girin

Tam sayı a

Modül m

Sonuç

Modular inverse a^-1 (mod m)

3

the integer x with a·x ≡ 1 (mod m)

gcd(a, m)	1
Kalan aralığı	0 ≤ x < m

Modüler Çarpımsal Ters Hesaplayıcı nedir?

Bu araç, bir a tam sayısının m modülüne göre çarpımsal tersini bulur; yani \(a \cdot x \equiv 1 \pmod{m}\) koşulunu sağlayan, \(0 \le x < m\) aralığındaki tek x tam sayısını hesaplar. Hesaplama için Genişletilmiş Öklid Algoritması kullanılır ve bu algoritma aynı zamanda en büyük ortak bölen \(\gcd(a, m)\) değerini de döndürür. Bu tamamen sayı teorisine dayanan bir işlemdir ve dünyanın her yerinde aynı şekilde çalışır. Kriptografide (RSA anahtar üretimi), karma (hash) işlemlerinde ve doğrusal denkliklerin (kongrüans) çözümünde sıkça kullanılır.

Nasıl kullanılır?

a tam sayısını ve pozitif bir m modülünü girin (anlamlı ve tek bir ters için \(m \ge 2\) olmalıdır). Araç önce a sayısını m modülüne göre indirger, ardından Genişletilmiş Öklid Algoritmasını çalıştırarak hem tersi hem de \(\gcd(a, m)\) değerini gösterir. Eğer a ile m aralarında asal değilse (\(\gcd \ne 1\)), ters mevcut değildir ve hesaplayıcı bunu açıkça belirtir.

Formülün açıklaması

Ters yalnızca ve yalnızca \(\gcd(a, m) = 1\) olduğunda vardır. Genişletilmiş Öklid Algoritması, \(a \cdot s + m \cdot t = \gcd(a, m)\) eşitliğini sağlayan s ve t tam sayılarını bulur. gcd değeri 1 olduğunda \(a \cdot s \equiv 1 \pmod{m}\) olur; dolayısıyla ters $$x = ((s \bmod m) + m) \bmod m$$ formülüyle bulunur ve en küçük negatif olmayan kalana normalize edilir.

Reklam

Ters x, a*x'in modülü dolanıp 1'e eşit olduğu değerdir.

Çözümlü örnek

\(a = 7\), \(m = 4\) için: \(7 \equiv 3 \pmod{4}\) olduğundan \(3x \equiv 1 \pmod{4}\) denklemini çözeriz. (7, 4) üzerinde Genişletilmiş Öklid Algoritması \(\gcd = 1\) ve Bézout katsayısı \(s = -1\) sonucunu verir; böylece $$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$ olur. Kontrol edelim: \(7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod{4}\). Sonuç 3'tür.

Genişletilmiş Öklid algoritması, tersi ve gcd(a, m)'yi tek işlemde bulur.

Sıkça Sorulan Sorular

Ters ne zaman bulunmaz? Yalnızca \(\gcd(a, m) > 1\) olduğunda. Örneğin \(a = 6\), \(m = 9\) için \(\gcd = 3\) olduğundan ters mevcut değildir.

a negatif veya m'den büyük olabilir mi? Evet. Önce a sayısını m modülüne göre indirgeriz; \(a \equiv a' \pmod{m}\) olduğundan sonuç değişmez.

m = 1 ise ne olur? Her tam sayı 1 modülüne göre 0'a denktir; bu nedenle ters basitçe 0 olur.