मिलर-रैबिन अभाज्यता परीक्षण एक क्लासिक विधि में फर्मेट परीक्षण और फर्मेट रूट परीक्षण को जोड़ता है एक मजबूत छद्म-अभाज्य खोजने के लिए। इस परीक्षण में, यह n - 1 को एक विषम संख्या m और 2 की शक्ति के गुणनफल के रूप में लिख सकता है:
$$\mathrm{n-1=m\, x\, 2^{k}}$$
आधार a में फर्मेट परीक्षण इस प्रकार लिखा जा सकता है:
$$\mathrm{a^{n-1}\, =\, a^{m\, x\, 2k}=\left [ a^{m} \right ]^{2k}=\left [ a^{m} \right ]\frac{2^{2}\cdot \cdot \cdot 2}{K\, times}}$$
दूसरे शब्दों में, an-1(mod n) की गणना एक चरण में करने के बजाय, यह इसे k+1 चरणों में कर सकता है। k + 1 का उपयोग करने का लाभ यह है कि प्रत्येक चरण में वर्गमूल चरण लागू किया जा सकता है। यदि वर्गमूल परीक्षण विफल होता है, तो यह रुक सकता है और n को मिश्रित संख्या घोषित कर सकता है।
प्रत्येक चरण में, यह प्रदान कर सकता है कि फर्मेट परीक्षण पास हो गया है और यदि सुलभ हो तो आसन्न चरणों के सभी समूह के बीच वर्गमूल परीक्षण संतुष्ट है (यदि परिणाम 1 है)।
आरंभीकरण
यह एक आधार a का चयन कर सकता है और $\mathrm{T\, =\, a^{m}}$ की गणना कर सकता है, जिसमें $\mathrm{m\, =\, \frac{n-1}{2^{k}}}$
यदि T +1 या -1 है तो घोषित करें कि n एक मजबूत छद्म-अभाज्य है और रुकें। क्योंकि यदि T +-1 है, तो T अगले चरण में 1 बन जाएगा और फर्मेट परीक्षण पास होने तक 1 रहेगा। इसके अलावा, T ने वर्गमूल परीक्षण पास कर लिया है क्योंकि T अगले चरण में 1 हो सकता है और 1 का वर्गमूल (अगले चरण में) +-1 है।
यदि T कुछ और है, तो यह सुनिश्चित नहीं है कि n अभाज्य है या मिश्रित, इसलिए यह अगले चरण पर जारी रख सकता है।
चरण 1: हम T का वर्ग करते हैं
यदि परिणाम +1 है, तो यह निश्चित रूप से ज्ञात है कि फर्मेट परीक्षण पास होगा क्योंकि T बाद के परीक्षणों के लिए 1 रहता है। वर्गमूल परीक्षण पास नहीं हुआ है। क्योंकि T इस चरण में 1 है और पिछले चरण में +-1 के अलावा कुछ और था, यह n को मिश्रित घोषित कर सकता है और रुक सकता है।
यदि परिणाम -1 है, तो यह समझ सकता है कि n अंततः फर्मेट परीक्षण पास करेगा। यह यह भी समझ सकता है कि यह वर्गमूल परीक्षण पास करेगा क्योंकि T इस चरण में -1 है और अगले चरण में 1 बन जाता है। यह n को मजबूत छद्म-अभाज्य घोषित कर सकता है और रुक सकता है।
यदि T कुछ और है, तो यह सुनिश्चित नहीं है कि यह कर सकता है या अभाज्य नहीं है। यह अगले चरण पर जारी रखता है।
चरण 2 से चरण K - 1:
यह चरण और सभी बाद के चरण चरण 2 से चरण K -1 तक चरण 1 के समान चलते रहते हैं।
चरण K:
यह चरण आवश्यक नहीं है। यदि यह इस चरण तक पहुंच गया है और इसने निर्णय नहीं लिया है, तो यह चरण हमें प्रदान नहीं करेगा। यदि इस चरण का परिणाम 1 है, तो फर्मेट परीक्षण स्वीकार किया जाता है, लेकिन क्योंकि पिछले चरण का परिणाम +-1 नहीं है, वर्गमूल परीक्षण स्वीकार नहीं किया जाता है। चरण k -1 के बाद, यदि यह पहले से नहीं रुका है, तो यह घोषित कर सकता है कि n मिश्रित है। मिलर-रैबिन परीक्षण चरण 0 से चरण K-1 तक आवश्यक है।
