ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट
ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट पहला पोलीनोमिअल टाइम है अल्गोरिद्म (कंप्यूटर विज्ञान में पोलीनोमिअल टाइम अल्गोरिद्मों को तेज माना जाता है[१][२][३]) जो बताता है कि कोई नंबर अभाज्य है या नहीं।[४] इसका आविष्कार 2002 में भारतीय प्रौद्योगिकी संस्थान कानपुर के तीन कंप्यूटर वैज्ञानिकों – मणीन्द्र अग्रवाल, नीरज कयाल और नितिन सक्सेना ने किया था।[५][६]
किसी भी अल्गोरिद्म के लिए चार आवश्यकताएँ होती है: 1) वो हर इनपुट के लिए आउटपुट देता हो, 2) वो जल्दी उत्तर देता हो (more precisely: वो पोलीनोमिअल टाइम में उत्तर देता हो), 3) वो कभी गलत उत्तर न देता हो और 4) वो किसी अप्रमाणित परिकल्पना पर निर्भर न करता हो। नंबर की अभाज्यता जांचने के लिए इस से पहले के सभी अल्गोरिद्म इन चार में से अधिक से अधिक तीन आवश्यकताओं को पूर्ण करते थे। ये पहला अल्गोरिद्म है जो इन चारों आवश्यकताओं को पूर्ण करता है।
- इस अल्गोरिद्म का प्रयोग किसी भी नंबर भी अभाज्यता जानने के लिए किया जा सकता है। इस से पहले के कई अल्गोरिद्म केवल खास श्रेणियों के नम्बरों के लिए काम करते हैं। उदाहरण के लिए लुकास-लेहमर टेस्ट सिर्फ मर्सेन नम्बरों के लिए काम करता है, और पेपिन टेस्ट सिर्फ फर्मेट नम्बरों के लिए।
- ये अल्गोरिद्म पोलिनोमिअल टाइम में उत्तर देता है। सरल भाषा में कहें तो ये कम समय में उत्तर दे देता है। इस से पहले ऐसे अल्गोरिद्म थे जो हर नंबर के लिए काम करते थे, पर पोलिनोमिअल टाइम में उत्तर नहीं देते थे। ऐसे अल्गोरिद्मों को 60 डिजिट के कुछ नम्बरों की अभाज्यता जांचने के लिए खरबों वर्ष लगेंगे, जो कि ब्रह्माण्ड की वर्तमान उम्र 13.82 अरब वर्ष से 100 गुणा है। अंडाकार वक्र पर आधारित अल्गोरिद्म और एडेलमैन–पोमेरेन्स–रुमली टेस्ट सभी नम्बरों के लिए काम करते हैं, पर उत्तर पोलिनोमिअल टाइम में नहीं दे पाते।
- ये अल्गोरिद्म कभी भी गलत उत्तर नहीं देता है। मिल्लर-रेबिन टेस्ट और बेल्ली-पीएसडब्ल्यू टेस्ट तेज हैं और हर नंबर के लिए काम करते हैं, पर उनकी गलत उत्तर देने की कुछ सम्भावना होती है।
- "ये अल्गोरिद्म कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए किसी अप्रमाणित परिकल्पना की जरुरत नहीं है। मिल्लर टेस्ट तेज है, हर नंबर के लिए काम करता है, किसी भी परीक्षण में उसे गलत उत्तर देते नहीं पाया गया है; पर "वो कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए एक अप्रमाणित परिकल्पना जनरलाइज़ड रीमन्न परिकल्पना की जरुरत है।
इन्हें भी देखें
सन्दर्भ
- ↑ साँचा:harvtxt
- ↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
- ↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
- ↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
- ↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
- ↑ Bornemann, Folkmar (2003). "PRIMES Is in P: A Breakthrough for "Everyman"" (PDF). Notices of the AMS (in अंग्रेज़ी). American Mathematical Society. 50 (5): 545–552. Archived (PDF) from the original on 27 दिसंबर 2015. Retrieved 26 दिसंबर 2015.
{{cite journal}}: Check date values in:|accessdate=and|archive-date=(help)
ग्रन्थ सूची
- स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।