Modüler çarpımsal ters nedir?
Bir a tam sayısının m modülüne göre çarpımsal tersi, \((a \cdot x) \bmod m = 1\) eşitliğini sağlayan ve 1 ile m−1 arasında yer alan bir x tam sayısıdır. Yani a'yı x ile çarpıp m'e böldüğünüzde kalan tam olarak 1 olur. Bu işlem, modüler aritmetikte bölme işleminin karşılığıdır ve sayılar teorisinin ile kriptografinin temel taşlarından biridir (RSA anahtar üretimi, özetleme/hashing, Çin Kalan Teoremi ve daha fazlası).
Bu hesaplayıcı nasıl kullanılır?
a tam sayısını ve m modülünü (m, 2 veya daha büyük olmalıdır) girin. Hesaplayıcı a'yı m modülüne göre indirger, genişletilmiş Öklid algoritmasını çalıştırır ve varsa tersi döndürür. a'nın negatif değerleri, 0 ile m−1 aralığına indirgenerek otomatik olarak işlenir.
Formülün açıklaması
Ters yalnızca ve yalnızca \(\gcd(a, m) = 1\) olduğunda var olur; yani a ile m'nin 1 dışında ortak böleni yoktur (aralarında asaldırlar). 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. Eğer gcd 1 ise, m modülüne göre indirgenen s katsayısı tersi verir. \(\gcd(a, m) \neq 1\) ise ters yoktur.
Çözümlü örnek
3 sayısının 11 modülüne göre tersini bulalım. \((3 \cdot x) \bmod 11 = 1\) koşulunu sağlayan x'i arıyoruz. Denediğimizde $$3 \cdot 4 = 12 \quad \text{ve} \quad 12 \bmod 11 = 1$$ olur. Demek ki ters 4'tür. \(\gcd(3, 11) = 1\) olduğundan genişletilmiş Öklid algoritması da aynı sonucu anında verir.
Sıkça Sorulan Sorular
Ne zaman ters bulunmaz? a ile m aralarında asal değilse. Örneğin \(\gcd(4, 8) = 4 \neq 1\) olduğundan 4'ün 8 modülüne göre tersi yoktur.
Modülün asal olması gerekir mi? Hayır. a ile aralarında asal olduğu sürece her modül işe yarar. Eğer m asal ise, 1 ile m−1 arasındaki sıfırdan farklı her a değerinin bir tersi vardır.
Sonuç neden her zaman 1 ile m−1 arasındadır? Çünkü tersi m modülüne göre indirgeyerek en küçük pozitif kanonik temsilciyi veririz.
