حساب المعكوس الضربي النمطية بكفاءة في بايثون

يُعدّ المُعاكس الضربي النمطّي مفهومًا أساسيًا في نظرية الأعداد والتشفير. إنه عدد، عند ضربه بعدد آخر وأخذ الباقي من قسمته على مُعامل معطى، يُعطي نتيجةً تساوي 1. تتناول هذه المقالة العديد من الخوارزميات الفعّالة لحساب المُعاكس الضربي النمطّي في بايثون، مُقارنةً كفاءتها وتطبيقها.

محتويات

1. الطريقة التكرارية البسيطة
2. الأسّ النمطّي (مبرهنة فيرما الصغيرة)
3. الخوارزمية الإقليدية المُوسّعة
4. الخلاصة

1. الطريقة التكرارية البسيطة

تتكرر هذه الطريقة البسيطة عبر المُعاكسات المُمكنة حتى تجد واحدةً تُرضي الشرط. وعلى الرغم من بساطة فهمها، إلا أن تعقيدها الزمني O(m) يجعلها غير فعّالة للغاية بالنسبة للمعاملات الكبيرة.

def modular_inverse_naive(a, m):
    """
    يحسب المُعاكس الضربي النمطّي باستخدام طريقة تكرارية بسيطة.

    Args:
        a: العدد الذي نريد إيجاد مُعاكسه.
        m: المُعامل.

    Returns:
        المُعاكس الضربي النمطّي لـ a مُعامل m، أو None إذا لم يوجد.
    """
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# مثال على الاستخدام
a = 3
m = 11
inverse = modular_inverse_naive(a, m)
print(f"المُعاكس الضربي النمطّي لـ {a} مُعامل {m} هو: {inverse}")  # الناتج: 4

2. الأسّ النمطّي (مبرهنة فيرما الصغيرة)

عندما يكون المُعامل m عددًا أوليًا، تُقدّم مبرهنة فيرما الصغيرة حلًا فعّالًا. تنصّ على أن a^p-1 ≡ 1 (mod p) لأي عدد صحيح a غير قابل للقسمة على p. لذلك، فإن المُعاكس هو a^p-2 (mod p)، والذي يُحسب بكفاءة باستخدام الأسّ النمطّي. تتميّز هذه الطريقة بتعقيد زمني قدره O(log m).

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")
  return modular_exponentiation(a, p - 2, p)

# مثال على الاستخدام (p عدد أولي)
a = 3
p = 11
inverse = modular_inverse_fermat(a, p)
print(f"المُعاكس الضربي النمطّي لـ {a} مُعامل {p} هو: {inverse}")  # الناتج: 4

3. الخوارزمية الإقليدية المُوسّعة

تُعدّ الخوارزمية الإقليدية المُوسّعة الطريقة الأكثر عموميةً وفعاليةً، وتُطبّق على أي مُعامل. تجد القاسم المشترك الأكبر (GCD) لعددين وتُعبّره كمجموعة خطية من هذين العددين. إذا كان القاسم المشترك الأكبر 1، فإن المُعاكس النمطّي موجود ويُحصل عليه بسهولة. تتميّز هذه الخوارزمية أيضًا بتعقيد زمني قدره O(log m).

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  # لا يوجد مُعاكس
    else:
        return x % m

# مثال على الاستخدام
a = 3
m = 11
inverse = modular_inverse_euclidean(a, m)
print(f"المُعاكس الضربي النمطّي لـ {a} مُعامل {m} هو: {inverse}")  # الناتج: 4

a = 5
m = 12
inverse = modular_inverse_euclidean(a, m)
print(f"المُعاكس الضربي النمطّي لـ {a} مُعامل {m} هو: {inverse}")  # الناتج: None

4. الخلاصة

قدّمت هذه المقالة ثلاث خوارزميات لحساب المُعاكس الضربي النمطّي. الطريقة البسيطة سهلة ولكنها غير فعّالة. تُقدّم مبرهنة فيرما الصغيرة حلًا فعّالًا للمعاملات الأولية. تُعدّ الخوارزمية الإقليدية المُوسّعة الطريقة الأكثر تنوعًا وفعاليةً، وتُطبّق على أي مُعامل حيث يوجد المُعاكس، مما يجعلها الخيار المُفضّل لمعظم التطبيقات، خاصةً في التشفير.