ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट
इस लेख में सुधार किया जा रहा है। इसकी भाषा को सरल बना दी जाएगा, और सन्दर्भ भी जोड़ दिए जाएंगे। थोड़ा समय दीजिए।
ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट पहला पोलीनोमिअल टाइम है अल्गोरिद्म (कंप्यूटर विज्ञान में पोलीनोमिअल टाइम अल्गोरिद्मों को तेज माना जाता है[1][2][3]) जो बताता है कि कोई नंबर अभाज्य है या नहीं।[4] इसका आविष्कार 2002 में भारतीय प्रौद्योगिकी संस्थान कानपुर के तीन कंप्यूटर वैज्ञानिकों – मणीन्द्र अग्रवाल, नीरज कयाल और नितिन सक्सेना ने किया था।[5][6]
किसी भी अल्गोरिद्म के लिए चार आवश्यकताएँ होती है: 1) वो हर इनपुट के लिए आउटपुट देता हो, 2) वो जल्दी उत्तर देता हो (more precisely: वो पोलीनोमिअल टाइम में उत्तर देता हो), 3) वो कभी गलत उत्तर न देता हो और 4) वो किसी अप्रमाणित परिकल्पना पर निर्भर न करता हो। नंबर की अभाज्यता जांचने के लिए इस से पहले के सभी अल्गोरिद्म इन चार में से अधिक से अधिक तीन आवश्यकताओं को पूर्ण करते थे। ये पहला अल्गोरिद्म है जो इन चारों आवश्यकताओं को पूर्ण करता है।
- इस अल्गोरिद्म का प्रयोग किसी भी नंबर भी अभाज्यता जानने के लिए किया जा सकता है। इस से पहले के कई अल्गोरिद्म केवल खास श्रेणियों के नम्बरों के लिए काम करते हैं। उदाहरण के लिए लुकास-लेहमर टेस्ट सिर्फ मर्सेन नम्बरों के लिए काम करता है, और पेपिन टेस्ट सिर्फ फर्मेट नम्बरों के लिए।
- ये अल्गोरिद्म पोलिनोमिअल टाइम में उत्तर देता है। सरल भाषा में कहें तो ये कम समय में उत्तर दे देता है। इस से पहले ऐसे अल्गोरिद्म थे जो हर नंबर के लिए काम करते थे, पर पोलिनोमिअल टाइम में उत्तर नहीं देते थे। ऐसे अल्गोरिद्मों को 60 डिजिट के कुछ नम्बरों की अभाज्यता जांचने के लिए खरबों वर्ष लगेंगे, जो कि ब्रह्माण्ड की वर्तमान उम्र 13.82 अरब वर्ष से 100 गुणा है। अंडाकार वक्र पर आधारित अल्गोरिद्म और एडेलमैन–पोमेरेन्स–रुमली टेस्ट सभी नम्बरों के लिए काम करते हैं, पर उत्तर पोलिनोमिअल टाइम में नहीं दे पाते।
- ये अल्गोरिद्म कभी भी गलत उत्तर नहीं देता है। मिल्लर-रेबिन टेस्ट और बेल्ली-पीएसडब्ल्यू टेस्ट तेज हैं और हर नंबर के लिए काम करते हैं, पर उनकी गलत उत्तर देने की कुछ सम्भावना होती है।
- "ये अल्गोरिद्म कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए किसी अप्रमाणित परिकल्पना की जरुरत नहीं है। मिल्लर टेस्ट तेज है, हर नंबर के लिए काम करता है, किसी भी परीक्षण में उसे गलत उत्तर देते नहीं पाया गया है; पर "वो कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए एक अप्रमाणित परिकल्पना जनरलाइज़ड रीमन्न परिकल्पना की जरुरत है।
इन्हें भी देखें
सन्दर्भ
- ↑ Arora & Barak (2009, p. 25, "Now we try to make the notion of “efficient computation” precise. We equate this with polynomial running time, which means it is at most n^c for some constant c > 0.")
- ↑ Papadimitriou, Christos H. (1994). Computational complexity (अंग्रेज़ी में) (Reprinted with corr., [Nachdr.] संस्करण). Reading, Mass. [u.a.]: Addison-Wesley. पपृ॰ 6. आई॰ऍस॰बी॰ऍन॰ 0-201-53082-1.
In the course of this book we shall regard such polynomial rates of growth as acceptable time requirements, as a sign that the problem has been solved satisfactorily.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "Polynomial time". Introduction to algorithms (अंग्रेज़ी में) (3rd ed. संस्करण). Cambridge, Massachusetts: MIT Press. पपृ॰ 1053-1054. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.सीएस1 रखरखाव: फालतू पाठ (link)
- ↑ "AKS Primality Test". MathWorld (अंग्रेज़ी में). Wolfram. मूल से 27 दिसंबर 2015 को पुरालेखित. अभिगमन तिथि 26 दिसंबर 2015.
- ↑ Robinson, Sara (8 अगस्त 2002). "New Method Said to Solve Key Problem in Math". New York Times (अंग्रेज़ी में). मूल से 27 दिसंबर 2015 को पुरालेखित. अभिगमन तिथि 26 दिसंबर 2015.
- ↑ Bornemann, Folkmar (2003). "PRIMES Is in P: A Breakthrough for "Everyman"" (PDF). Notices of the AMS (अंग्रेज़ी में). American Mathematical Society. 50 (5): 545–552. मूल से 27 दिसंबर 2015 को पुरालेखित (PDF). अभिगमन तिथि 26 दिसंबर 2015.
ग्रन्थ सूची
- Shoup, Victor (2009). "Chapter 21: Deterministic primality testing". A computational introduction to number theory and algebra (PDF) (अंग्रेज़ी में) (2nd ed. संस्करण). Cambridge University Press. आई॰ऍस॰बी॰ऍन॰ 9780521516440. मूल (PDF) से 3 फ़रवरी 2016 को पुरालेखित. अभिगमन तिथि 27 दिसंबर 2015.सीएस1 रखरखाव: फालतू पाठ (link)