एक अभाज्यता परीक्षण एक एल्गोरिदम है जो यह तय करता है कि एक इनपुट संख्या अभाज्य है या नहीं। कुछ अभाज्यता परीक्षण निश्चितात्मक हैं। वे हमेशा सही ढंग से तय करते हैं कि कोई संख्या अभाज्य है या मिश्रित।
सबसे तेज़ ज्ञात निश्चितात्मक अभाज्यता परीक्षण 2004 में आविष्कृत किया गया था। तीन कंप्यूटर वैज्ञानिक, जैसे अग्रवाल, कायल, और सक्सेना, ने AKS अभाज्यता परीक्षण का आविष्कार किया जो Õ(log(n)⁶) समय में संचालित होता है, जहां Õ(f(n)) को O(f(n)·log(f(n))ᵏ) के रूप में दर्शाया जाता है कुछ पूर्णांक k [1] के लिए। हालांकि एक महत्वपूर्ण सफलता, यह गति सूचना सुरक्षा आवश्यकता की तुलना मेंrather धीमी है।
अभाज्य संख्याओं का लाभ यह है कि वे क्रिप्टोग्राफी में उपयोग की जाती हैं। मानक क्रिप्टोसिस्टम में से एक - RSA एल्गोरिदम को कुंजी के रूप में एक अभाज्य संख्या की आवश्यकता होती है जो आमतौर पर उच्च सुरक्षा प्रदान करने के लिए 1024 बिट्स से अधिक होती है।
ऐसी बड़ी संख्याओं से निपटने पर, निश्चित रूप से निम्नलिखित विधि कोई अच्छी नहीं बनाती है। अभाज्यता परीक्षण के समय / और % संचालन किए जाने पर ऐसी बड़ी संख्याओं के साथ काम करना विशेष रूप से आसान नहीं है।
इसलिए, उत्पादित सर्वोत्तम अभाज्यता परीक्षण एल्गोरिदम केवल यह तय कर सकते हैं कि प्रदान की गई संख्या एक "संभावित अभाज्य" है या मिश्रित।
अभाज्यता परीक्षण के निम्नलिखित प्रकार हैं:
निश्चितात्मक एल्गोरिदम - एक निश्चितात्मक अभाज्यता परीक्षण एल्गोरिदम एक पूर्णांक स्वीकार करता है और लगातार एक अभाज्य या मिश्रित आउटपुट करता है। यह एल्गोरिदम हमेशा उचित उत्तर देता है।
विभाज्यता एल्गोरिदम - सबसे सरल अभाज्यता परीक्षण निम्नानुसार है:
एक इनपुट संख्या n दिए जाने पर, जांचें कि क्या 2 से n-1 तक का कोई पूर्णांक n को विभाजित करता है। यदि n किसी m से विभाज्य है, तो n मिश्रित है अन्यथा यह अभाज्य है। हालांकि, n-1 तक सभी m का परीक्षण करने के बजाय, केवल m का परीक्षण √n तक करना महत्वपूर्ण है। यदि n मिश्रित है तो इसे दो मानों में विभाजित किया जा सकता है, जिनमें से कम से कम एक √n से कम या बराबर होना चाहिए।
संभाव्य एल्गोरिदम - एक संभाव्य एल्गोरिदम एक उत्तर प्रदान करता है जो अधिकांश समय सही होता है, लेकिन हर समय नहीं। ये परीक्षण तय करते हैं कि n एक या अधिक शर्तों को संतुष्ट करता है जो सभी अभाज्य संख्याओं को संतुष्ट करना चाहिए। एक संभाव्य एल्गोरिदम निम्नलिखित नियमों के आधार पर या तो अभाज्य या मिश्रित लौटाता है:
यदि परीक्षण की जाने वाली पूर्णांक वास्तव में अभाज्य है, तो एल्गोरिदम निश्चित रूप से अभाज्य लौटाता है।
यदि परीक्षण की जाने वाली पूर्णांक वास्तव में मिश्रित है, तो यह संभावना 1 - ε के साथ मिश्रित लौटाता है, लेकिन यह संभावना ε के साथ अभाज्य लौटा सकता है। त्रुटि की संभावना को कम किया जा सकता है यदि एल्गोरिदम को 'm' बार चलाया जाए और त्रुटि की संभावना Σᵐ तक कम हो जाए।
फर्मेट अभाज्यता परीक्षण - फर्मेट अभाज्यता परीक्षण फर्मेट के छोटे प्रमेय से उपजा है, जिसमें कहा गया है कि यदि n अभाज्य है, तो an-1 ≡ 1 (mod n)। एक इनपुट n और a < n दिए जाने पर, यह जांच सकता है कि क्या an-1 ≡ 1 (mod n)। यदि यह सच नहीं है, तो n मिश्रित है और n संभावित अभाज्य है। दुर्भाग्य से, फर्मेट अभाज्यता परीक्षण में त्रुटि की उच्च लागत है, बहुत सारे मिश्रित संभावित अभाज्य हो रहे हैं।
