एक प्रारंभिक परीक्षण यह तय करने के लिए एक एल्गोरिदम है कि इनपुट नंबर प्राइम है या नहीं। कुछ प्रारंभिक परीक्षण नियतात्मक हैं। वे हमेशा सही ढंग से तय करते हैं कि कोई संख्या अभाज्य है या मिश्रित।
सबसे तेज़ ज्ञात नियतात्मक प्रारंभिक परीक्षण का आविष्कार 2004 में किया गया था। तीन कंप्यूटर वैज्ञानिक हैं, जैसे अग्रवाल, कयाल और सक्सेना ने एकेएस प्रिमलिटीटेस्ट का आविष्कार किया जो ओ˜ (लॉग (एन) 6 में संचालित होता है। ) समय, जहां O˜ (f(n)) को O(f(n).log(f(n)) k के रूप में दर्शाया जाता है ) कुछ पूर्णांक k [1] के लिए। हालांकि एक महत्वपूर्ण सफलता, सूचना सुरक्षा आवश्यकता की तुलना में यह गति धीमी है।
अभाज्य संख्याओं का लाभ यह है कि उनका उपयोग क्रिप्टोग्राफी में किया जाता है। मानक क्रिप्टोसिस्टम में से एक -आरएसए एल्गोरिदम को कुंजी के रूप में एक प्रमुख संख्या की आवश्यकता होती है जो आमतौर पर उच्च सुरक्षा प्रदान करने के लिए 1024 बिट्स से अधिक होती है।
इतनी बड़ी संख्या से निपटने पर, निश्चित रूप से निम्न विधि को कोई अच्छा नहीं बनाता है। यह केवल इतनी बड़ी संख्या के साथ काम करने के लिए नहीं है, खासकर जब प्रदर्शन किए गए संचालन / और% प्रारंभिक परीक्षण के समय होते हैं।
इसलिए, उत्पादित किए जाने वाले सर्वोत्तम प्रारंभिक परीक्षण एल्गोरिदम केवल यह तय कर सकते हैं कि प्रदान की गई संख्या "संभावित प्राइम" या समग्र है या नहीं।
प्रिमलिटी टेस्टिंग के निम्नलिखित प्रकार हैं जो इस प्रकार हैं -
-
निर्धारक एल्गोरिथम - एक नियतात्मक प्रारंभिक परीक्षण एल्गोरिथ्म एक पूर्णांक को स्वीकार करता है और लगातार एक प्रमुख या एक समग्र उत्पादन करता है। यह एल्गोरिथम हमेशा एक उचित उत्तर प्रदान करता है।
-
विभाज्यता एल्गोरिदम − सरलतम प्रारंभिक परीक्षण इस प्रकार है -
एक इनपुट संख्या n को देखते हुए, जाँचता है कि क्या 2 से n -1 तक का कोई पूर्णांक n को विभाजित करता है। यदि n किसी m से विभाज्य है, तो n सम्मिश्र है अन्यथा यह एक अभाज्य है। हालांकि, n - 1 तक सभी m का परीक्षण करने के बजाय, केवल m को n तक जांचना महत्वपूर्ण है। यदि n मिश्रित है तो इसे दो मानों में विभाजित किया जा सकता है, जिनमें से कम से कम एक √n से कम या समान होना चाहिए।
-
संभाव्य एल्गोरिथम - एक संभाव्य एल्गोरिथम एक ऐसा उत्तर प्रदान करता है जो अधिकांश समय सही होता है, लेकिन सभी समय नहीं। इन परीक्षणों ने तय किया कि क्या n एक या अधिक शर्तों को पूरा करता है जो सभी प्राइम को संतुष्ट करना चाहिए। एक संभाव्य एल्गोरिथ्म या तो एक प्राइम या एक समग्र को पुनर्स्थापित करता है, निम्नलिखित नियमों पर निर्भर करता है -
-
यदि परीक्षण किया जाने वाला पूर्णांक वास्तव में एक अभाज्य है, तो एल्गोरिथम निश्चित रूप से वापस आ जाता है।
-
यदि परीक्षण किया जाने वाला पूर्णांक वास्तव में एक समग्र है, तो यह संभाव्यता 1 - के साथ एक समग्र देता है, लेकिन यह संभावना ε के साथ एक प्रमुख वापस कर सकता है। गलतियों की संभावना को बढ़ाया जा सकता है यदि यह एल्गोरिथम 'एम' बार चला सकता है और त्रुटि की संभावना Σ m तक कम हो जाती है ।
-
फर्मेट प्राइमलिटी टेस्ट - फ़र्मेट प्रिमलिटी टेस्ट फ़र्मेट के लिटिल थ्योरम से उपजा है, जिसमें कहा गया है कि अगर n प्राइम है, तो a
n−1
1 (मॉड एन)। इनपुट n और a