Fermat's Little Theorem in Cryptography in Hindi: प्रमेय, प्रमाण और उपयोग

Fermat's Little Theorem in Cryptography: प्रमेय, प्रमाण और उपयोग

परिचय

Fermat's Little Theorem (फरमेट का लघु प्रमेय) संख्यात्मक सिद्धांत (Number Theory) का एक महत्वपूर्ण प्रमेय है, जिसका उपयोग Cryptography में विभिन्न एन्क्रिप्शन और डिक्रिप्शन प्रक्रियाओं में किया जाता है। विशेष रूप से **RSA एल्गोरिदम**, **प्राइम नंबर टेस्टिंग**, और **मॉड्यूलर गणना** में यह प्रमेय महत्वपूर्ण भूमिका निभाता है।

1. Fermat's Little Theorem क्या है?

Fermat's Little Theorem कहता है कि यदि **p** एक प्राइम संख्या है और **a** कोई भी संख्या है जो **p** से विभाज्य नहीं है, तो:

[ a^{p-1} equiv 1 mod p ]

इसका मतलब है कि यदि हम a को (p-1) घात तक बढ़ाकर p से विभाजित करें, तो हमें शेष 1 मिलेगा।

1.1 विशेष रूप:

• यदि p एक प्राइम संख्या है, तो किसी भी पूर्णांक **a** के लिए:
• [ a^p equiv a mod p ]
• यदि a, p का गुणज (multiple) नहीं है, तो:
• [ a^{p-1} equiv 1 mod p ]

2. Fermat's Theorem का प्रमाण

इस प्रमेय का प्रमाण गणितीय आगमन (Mathematical Induction) और मॉड्यूलर अंकगणित के उपयोग से किया जाता है। आइए इसे प्रमाणित करें:

[ a^{p} equiv a mod p ]

हम पूर्णांक गुणनखंडों (Integer Multiples) का उपयोग करके दिखा सकते हैं कि:

[ a^{p-1} equiv 1 mod p ]

यह प्रमेय Lagrange's Theorem पर भी आधारित है, जो कहता है कि यदि **G** एक ग्रुप है और |G| उसका ऑर्डर है, तो किसी भी a ∈ G के लिए **a^|G| = 1** होता है।

3. क्रिप्टोग्राफी में Fermat's Little Theorem का उपयोग

3.1 RSA एल्गोरिदम (RSA Algorithm)

RSA एल्गोरिदम **Asymmetric Key Cryptography** का एक महत्वपूर्ण भाग है। इस एल्गोरिदम में प्राइम नंबरों का उपयोग **Encryption** और **Decryption** के लिए किया जाता है।

• Fermat's Theorem RSA में मॉड्यूलर इन्वर्स (Modular Inverse) की गणना के लिए उपयोग किया जाता है।
• यदि p और q दो बड़े प्राइम नंबर हैं, तो उनका गुणनफल n = p × q होता है।
• Euler's Totient Function के अनुसार, (phi(n) = (p-1)(q-1)) होता है।
• RSA में, Fermat's Theorem का उपयोग निजी (private) कुंजी निकालने के लिए किया जाता है।

3.2 प्राइम नंबर की जाँच (Primality Testing)

Fermat's Little Theorem का उपयोग **Miller-Rabin Test** और **Fermat Primality Test** में किया जाता है, जो यह जाँचने के लिए प्रयोग किए जाते हैं कि कोई संख्या प्राइम है या नहीं।

उदाहरण:

मान लीजिए, हमें जाँचना है कि 7 एक प्राइम संख्या है या नहीं:

किसी भी संख्या **a** के लिए, यदि:

[ a^6 equiv 1 mod 7 ]

तो 7 एक प्राइम संख्या होगी।

3.3 मॉड्यूलर इन्वर्स (Modular Inverse)

Fermat's Little Theorem का उपयोग मॉड्यूलर इन्वर्स निकालने के लिए किया जाता है। किसी संख्या **a** का मॉड्यूलर इन्वर्स **p** के लिए:

[ a^{-1} equiv a^{p-2} mod p ]

उदाहरण:

अगर हमें **3 का मॉड्यूलर इन्वर्स 7 के प्रति निकालना हो**, तो:

[ 3^{-1} equiv 3^{5} mod 7 ]

गणना करें:

• ( 3^5 = 243 )
• ( 243 mod 7 = 243 div 7 = 34, शेष 5 )

तो, **3 का मॉड्यूलर इन्वर्स 7 के लिए 5 होगा।**

निष्कर्ष

Fermat's Little Theorem क्रिप्टोग्राफी में विभिन्न महत्वपूर्ण एल्गोरिदम जैसे कि **RSA, प्राइम नंबर जाँच, और मॉड्यूलर इन्वर्स** के लिए उपयोगी है। यह प्रमेय एन्क्रिप्शन और डिक्रिप्शन प्रक्रियाओं में गणितीय रूप से महत्वपूर्ण भूमिका निभाता है।