मिलर राबिन बड़ी संख्या की प्रारंभिकता का परीक्षण करने के लिए एक तेज़ दृष्टिकोण है। इस एल्गोरिथम को राबिन-मिलर प्रिमलिटी टेस्ट कहा जाता है और यह एल्गोरिथम तय करता है कि नंबर प्राइम है या नहीं, जो कि फ़र्मेट प्रिमलिटी टेस्ट और सोलोवे- स्ट्रैसेन प्रिमलिटी टेस्ट सहित अन्य परीक्षणों के समान है।
यह परीक्षण समानता या समानता के समूह पर आधारित है जो अभाज्य मूल्यों के लिए सत्य रखता है, इस प्रकार जांचता है कि क्या वे संख्या के लिए धारण करते हैं, कि यह प्रारंभिकता के परीक्षण के लिए आवश्यक है।
यह एल्गोरिथम सबसे उपयोगी ज्ञात प्रारंभिक परीक्षण एल्गोरिथम है और इसका उपयोग विभिन्न सॉफ़्टवेयर लाइब्रेरी में किया जा सकता है जो आरएसए एन्क्रिप्शन पर आधारित है और सबसे अच्छा उदाहरण ओपनएसएसएल है।
मिलर राबिन पुष्टि करते हैं कि संख्या समग्र है। तो इसे प्रारंभिक परीक्षण के बजाय समग्रता परीक्षण कहा जाता है। मिलर राबिन परीक्षण सभी कंपोजिट की पहचान करता है। प्रत्येक समग्र संख्या n के लिए, संख्याओं के कम से कम 3/4 (मिलर राबिन) हो सकते हैं जो n की समग्रता के गवाह हैं।
मिलर राबिन फ़र्मेट्स लिटिल थ्योरम का सहयोगी रूप से सरल विस्तार है जो हमें फ़र्मेट्स लिटिल थ्योरम की तुलना में बहुत बड़ी संभावना के साथ प्राइमलिटी के लिए परीक्षण करने में सक्षम बनाता है।
एल्गोरिदम :मिलर-राबिन परीक्षण के लिए स्यूडोकोड -
Miller-Rabin-Test (n, a) // n is the number; a is the base
{
Find m and k such that n − 1 = m x 2k
T ← am mod n
If (T = ±1)return "a prime"
for (i ← 1 to k − 1) // k – 1 is the maximum number of steps
{
T ← T2 mod n
if (T = ±1) return "a composite"
if (T = −1) return "a prime"
}
return "a composite"
} वहाँ पूर्वi यह इस बात का प्रमाण देता है कि हर बार जब कोई संख्या मिलर-राबिन परीक्षण से गुजरती है, तो इसके अभाज्य नहीं होने की प्रायिकता है। यदि संख्या एम परीक्षण पास करती है (एम अलग-अलग पास के साथ), संभावना है कि अभाज्य नहीं है (1/4) m ।
उदाहरण :आधार 2 का उपयोग करके मिलर-राबिन एल्गोरिथम लागू करें ताकि यह जांचा जा सके कि संख्या 341 संयुक्त है या नहीं।
समाधान :मिलर-राबिन एल्गोरिथम का उपयोग करके, हम संख्या 341 का परीक्षण इस प्रकार कर सकते हैं:
Step1:341 - 1 =2 2 x 85. इस प्रकार p =341, k =2 और q =85
Step2:x =2 (दिया गया)
चरण 3:एस =एक्स q मॉड पी
=2 85 मॉड 341 =(2 10 ) x 2 5 मॉड 341 8
=2 10 मॉड 341 x 2 13 मॉड 341
=1 x 8192 मॉड 341 =8192 मॉड 341
=8
Step4:8 1 के रूप में, हम अगले चरण पर जाते हैं।
Step5:j =1 के लिए, S =x 2q मॉड पी
=2 170 मॉड 341 =(2 20 ) 8 x 2 10 मॉड 341
=2 20 मॉड 341 x 2 8 मॉड 341 x 2 10 मॉड 341
=1 x 256 x 1 =256
अब, =256 1
और परिणाम अनिर्णायक है
अतः, 341 एक भाज्य संख्या नहीं है।
फायदे
-
इस एल्गोरिथम का उपयोग प्रारंभिकता के लिए उच्च संख्याओं का परीक्षण करने के लिए किया जा सकता है।
-
अन्य प्रारंभिक परीक्षणों की तुलना में गति में इसके लाभ के कारण, मिलर राबिन परीक्षण कई क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए पसंद का परीक्षण होगा।
-
यूलर और सोलोवे-स्ट्रैसन परीक्षणों की तुलना में, मिलर राबिन अधिक गतिशील है और आवश्यक पहलू यह है कि विफलता की संभावना कम हो जाती है।
-
फ़र्मेट परीक्षण के अनुसार सभी कारमाइकलनंबर n के लिए बहुत अधिक झूठे हैं, त्रुटि संभावना 1 के करीब है, इस नुकसान को मिलर राबिन में रोका गया है।