Python’da Verimli Modüler Çarpımsal Ters Çevirme Hesaplama

Modüler çarpımsal ters, sayılar teorisi ve kriptografide temel bir kavramdır. Başka bir sayıyla çarpıldığında ve verilen bir modül üzerinden modulo alındığında sonucu 1 veren bir sayıdır. Bu makale, Python’da modüler çarpımsal tersi hesaplamak için çeşitli verimli algoritmaları inceleyerek, verimliliklerini ve uygulanabilirliklerini karşılaştırmaktadır.

İçindekiler

1. Basit İteratif Yaklaşım
2. Modüler Üstel Alma (Fermat’ın Küçük Teoremi)
3. Genişletilmiş Öklid Algoritması
4. Sonuç

1. Basit İteratif Yaklaşım

Bu basit yaklaşım, koşulu sağlayan birini bulana kadar olası tersleri yineleyerek işler. Anlaşılması basit olmasına rağmen, O(m) zaman karmaşıklığı büyük modüller için oldukça verimsiz hale getirir.

def modular_inverse_naive(a, m):
    """
    Basit iteratif bir yaklaşım kullanarak modüler çarpımsal tersi hesaplar.

    Args:
        a: Tersinin bulunacağı sayı.
        m: Modül.

    Returns:
        a'nın m modülüne göre modüler çarpımsal tersi veya mevcut değilse None.
    """
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# Örnek kullanım
a = 3
m = 11
inverse = modular_inverse_naive(a, m)
print(f"{a} sayısının {m} modülüne göre modüler çarpımsal tersi: {inverse}")  # Çıktı: 4

2. Modüler Üstel Alma (Fermat’ın Küçük Teoremi)

Modül m asal olduğunda, Fermat’ın Küçük Teoremi verimli bir çözüm sunar. p ile bölünemeyen herhangi bir tamsayı a için a^p-1 ≡ 1 (mod p) olduğunu belirtir. Bu nedenle, ters, modüler üstel alma kullanılarak verimli bir şekilde hesaplanabilen a^p-2 (mod p)’dir. Bu yöntemin zaman karmaşıklığı O(log m)’dir.

def modular_exponentiation(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return res

def modular_inverse_fermat(a, p):
  if p <= 1:
    raise ValueError("p, 1'den büyük bir asal sayı olmalıdır")
  return modular_exponentiation(a, p - 2, p)

# Örnek kullanım (p asal)
a = 3
p = 11
inverse = modular_inverse_fermat(a, p)
print(f"{a} sayısının {p} modülüne göre modüler çarpımsal tersi: {inverse}")  # Çıktı: 4

3. Genişletilmiş Öklid Algoritması

Genişletilmiş Öklid Algoritması, herhangi bir modüle uygulanabilen en genel ve verimli yöntemdir. İki sayının en büyük ortak bölenini (EBOB) bulur ve bunu bu sayıların doğrusal bir kombinasyonu olarak ifade eder. EBOB 1 ise, modüler ters mevcuttur ve kolayca elde edilir. Bu algoritmanın zaman karmaşıklığı da O(log m)’dir.

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modular_inverse_euclidean(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # Ters mevcut değil
    else:
        return x % m

# Örnek kullanım
a = 3
m = 11
inverse = modular_inverse_euclidean(a, m)
print(f"{a} sayısının {m} modülüne göre modüler çarpımsal tersi: {inverse}")  # Çıktı: 4

a = 5
m = 12
inverse = modular_inverse_euclidean(a, m)
print(f"{a} sayısının {m} modülüne göre modüler çarpımsal tersi: {inverse}")  # Çıktı: None

4. Sonuç

Bu makale, modüler çarpımsal tersi hesaplamak için üç algoritma sundu. Basit yaklaşım basit ancak verimsizdir. Fermat’ın Küçük Teoremi, asal modüller için verimli bir çözüm sunar. Genişletilmiş Öklid Algoritması, tersinin mevcut olduğu herhangi bir modüle uygulanabilen en çok yönlü ve verimli yöntemdir ve özellikle kriptografide çoğu uygulama için tercih edilen seçimdir.