मिलर रैबिन बड़ी संख्याओं की अभाज्यता का परीक्षण करने का एक तेज़ दृष्टिकोण है। इस एल्गोरिदम को रैबिन-मिलर अभाज्यता परीक्षण कहा जाता है और यह एल्गोरिदम तय करता है कि संख्या अभाज्य है या नहीं जो फर्मेट अभाज्यता परीक्षण और सोलोवे-स्ट्रासेन अभाज्यता परीक्षण जैसे अन्य परीक्षणों के समान है।
यह परीक्षण समानता या समानता के समूह पर आधारित है जो अभाज्य मानों के लिए सही हैं, इस प्रकार जांचते हैं कि क्या वे उस संख्या के लिए मान्य हैं जिसका अभाज्यता के लिए परीक्षण करना आवश्यक है।
यह एल्गोरिदम सबसे उपयोगी ज्ञात अभाज्यता परीक्षण एल्गोरिदम है और विभिन्न सॉफ्टवेयर लाइब्रेरी में उपयोग किया जा सकता है जो RSA एन्क्रिप्शन पर आधारित हैं और सबसे अच्छा उदाहरण OpenSSL है।
मिलर रैबिन मान्य करता है कि संख्या मिश्रित है। इसलिए इसे अभाज्यता परीक्षण के बजाय मिश्रितता परीक्षण कहा जाता है। मिलर रैबिन परीक्षण सभी मिश्रित संख्याओं की पहचान करता है। प्रत्येक मिश्रित संख्या n के लिए, कम से कम 3/4 (मिलर रैबिन) संख्याएं a, n की मिश्रितता के गवाह हो सकती हैं।
मिलर रैबिन फर्मेट के छोटे प्रमेय का अपेक्षाकृत सरल विस्तार है जो हमें फर्मेट के छोटे प्रमेय की तुलना में बहुत बड़ी संभावना के साथ अभाज्यता के लिए परीक्षण करने में सक्षम बनाता है।
एल्गोरिदम: मिलर-रैबिन परीक्षण के लिए छद्म कोड:
Miller-Rabin-Test (n, a) // n संख्या है; a आधार है { m और k ढूंढें जैसे कि n - 1 = m x 2k T ← am mod n If (T = ±1) return "एक अभाज्य" for (i ← 1 to k - 1) // k - 1 अधिकतम चरणों की संख्या है { T ← T2 mod n if (T = ±1) return "एक मिश्रित" if (T = -1) return "एक अभाज्य" } return "एक मिश्रित" } एक सबूत मौजूद है कि हर बार जब कोई संख्या मिलर-रैबिन परीक्षण पास करती है, तो इसकी संभावना कि यह अभाज्य नहीं है ¼ है। यदि संख्या m परीक्षण पास करती है (m अलग पास के साथ), तो इसकी संभावना कि यह अभाज्य नहीं है (1/4)m है।
उदाहरण: आधार 2 का उपयोग करके मिलर-रैबिन एल्गोरिदम लागू करें ताकि यह परीक्षण किया जा सके कि संख्या 341 मिश्रित है या नहीं।
समाधान: मिलर-रैबिन एल्गोरिदम का उपयोग करके, हम संख्या 341 का परीक्षण निम्नानुसार कर सकते हैं:
चरण 1: 341 - 1 = 2² x 85। इस प्रकार p = 341, k = 2 और q = 85
चरण 2: x = 2 (दिया गया)
चरण 3: S = xq mod p
= 285 mod 341 = (210) x 25 mod 341 8
= 210 mod 341 x 213 mod 341
= 1 x 8192 mod 341 = 8192 mod 341
= 8
चरण 4: चूंकि 8 ≠ 1, हम अगले चरण पर जाते हैं।
चरण 5: j = 1 के लिए, S = x2q mod p
= 2170 mod 341 = (220)8 x 210 mod 341
= 220 mod 341 x 28 mod 341 x 210 mod 341
= 1 x 256 x 1 = 256
अब, = 256 ≠ 1
और परिणाम अनिर्णायक है
तो, 341 मिश्रित संख्या नहीं है।
फायदे
इस एल्गोरिदम का उपयोग उच्च संख्याओं की अभाज्यता के लिए परीक्षण करने के लिए किया जा सकता है।
अन्य अभाज्यता परीक्षणों की तुलना में गति में इसके लाभ के कारण, मिलर रैबिन परीक्षण कई क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए पसंद का परीक्षण होगा।
यूलर और सोलोवे-स्ट्रासेन परीक्षणों की तुलना में, मिलर रैबिन अधिक गतिशील है और आवश्यक पहलू यह है कि विफलता की संभावना कम हो जाती है।
फर्मेट परीक्षण के अनुसार सभी कार्माइकल संख्याओं n के लिए बहुत सारे झूठे हैं, त्रुटि संभावना 1 के करीब है, यह नुकसान मिलर रैबिन में रोका जाता है।
