Python में कुशल मॉड्यूलर गुणात्मक प्रतिलोम गणना

मॉड्यूलर गुणात्मक प्रतिलोम संख्या सिद्धांत और क्रिप्टोग्राफी में एक मौलिक अवधारणा है। यह एक ऐसी संख्या है, जिसे किसी अन्य संख्या से गुणा करने और दिए गए मॉड्यूलस को लेने पर, 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) ज्ञात करता है और इसे उन संख्याओं के रैखिक संयोजन के रूप में व्यक्त करता है। यदि 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. निष्कर्ष

इस लेख में मॉड्यूलर गुणात्मक प्रतिलोम की गणना के लिए तीन एल्गोरिदम प्रस्तुत किए गए हैं। सरल दृष्टिकोण सरल लेकिन अकुशल है। फर्माट की छोटी प्रमेय अभाज्य मॉड्यूल के लिए एक कुशल समाधान प्रदान करती है। विस्तारित यूक्लिडियन एल्गोरिथम सबसे बहुमुखी और कुशल विधि है, जो किसी भी मॉड्यूलस पर लागू होती है जहाँ प्रतिलोम मौजूद है, जिससे यह अधिकांश अनुप्रयोगों, विशेष रूप से क्रिप्टोग्राफी में पसंदीदा विकल्प बन जाता है।