ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट

इस लेख में सुधार किया जा रहा है। इसकी भाषा को सरल बना दी जाएगा, और सन्दर्भ भी जोड़ दिए जाएंगे। थोड़ा समय दीजिए। ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट पहला पोलीनोमिअल टाइम है अल्गोरिद्म (कंप्यूटर विज्ञान में पोलीनोमिअल टाइम अल्गोरिद्मों को तेज माना जाता है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. Computational complexity https://archive.org/details/computationalcom00papa 1994 Addison-Wesley Reading, Mass. [u.a.] 0-201-53082-1 6 Reprinted with corr., [Nachdr.] अंग्रेज़ी 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 Introduction to algorithms https://archive.org/details/introductiontoal00corm_805 Polynomial time 2009 MIT Press Cambridge, Massachusetts 978-0-262-03384-8 1053-1054 3rd ed. अंग्रेज़ी) जो बताता है कि कोई नंबर अभाज्य है या नहीं।AKS Primality Test http://mathworld.wolfram.com/AKSPrimalityTest.html MathWorld Wolfram 26 दिसंबर 2015 अंग्रेज़ी https://web.archive.org/web/20151227154947/http://mathworld.wolfram.com/AKSPrimalityTest.html 27 दिसंबर 2015 live इसका आविष्कार 2002 में भारतीय प्रौद्योगिकी संस्थान कानपुर के तीन कंप्यूटर वैज्ञानिकों – मणीन्द्र अग्रवाल, नीरज कयाल और नितिन सक्सेना ने किया था।Robinson Sara New Method Said to Solve Key Problem in Math http://www.nytimes.com/2002/08/08/science/08MATH.html 26 दिसंबर 2015 अंग्रेज़ी New York Times 8 अगस्त 2002 https://web.archive.org/web/20151227150006/http://www.nytimes.com/2002/08/08/science/08MATH.html 27 दिसंबर 2015 liveBornemann Folkmar PRIMES Is in P: A Breakthrough for "Everyman" Notices of the AMS 2003 50 5 545-552 http://www.ams.org/journals/notices/200305/fea-bornemann.pdf 26 दिसंबर 2015 अंग्रेज़ी American Mathematical Society https://web.archive.org/web/20151227150000/http://www.ams.org/journals/notices/200305/fea-bornemann.pdf 27 दिसंबर 2015 live किसी भी अल्गोरिद्म के लिए चार आवश्यकताएँ होती है: 1) वो हर इनपुट के लिए आउटपुट देता हो, 2) वो जल्दी उत्तर देता हो (more precisely: वो पोलीनोमिअल टाइम में उत्तर देता हो), 3) वो कभी गलत उत्तर न देता हो और 4) वो किसी अप्रमाणित परिकल्पना पर निर्भर न करता हो। नंबर की अभाज्यता जांचने के लिए इस से पहले के सभी अल्गोरिद्म इन चार में से अधिक से अधिक तीन आवश्यकताओं को पूर्ण करते थे। ये पहला अल्गोरिद्म है जो इन चारों आवश्यकताओं को पूर्ण करता है। इस अल्गोरिद्म का प्रयोग किसी भी नंबर भी अभाज्यता जानने के लिए किया जा सकता है। इस से पहले के कई अल्गोरिद्म केवल खास श्रेणियों के नम्बरों के लिए काम करते हैं। उदाहरण के लिए लुकास-लेहमर टेस्ट सिर्फ मर्सेन नम्बरों के लिए काम करता है, और पेपिन टेस्ट सिर्फ फर्मेट नम्बरों के लिए। ये अल्गोरिद्म पोलिनोमिअल टाइम में उत्तर देता है। सरल भाषा में कहें तो ये कम समय में उत्तर दे देता है। इस से पहले ऐसे अल्गोरिद्म थे जो हर नंबर के लिए काम करते थे, पर पोलिनोमिअल टाइम में उत्तर नहीं देते थे। ऐसे अल्गोरिद्मों को 60 डिजिट के कुछ नम्बरों की अभाज्यता जांचने के लिए खरबों वर्ष लगेंगे, जो कि ब्रह्माण्ड की वर्तमान उम्र 13.82 अरब वर्ष से 100 गुणा है। अंडाकार वक्र पर आधारित अल्गोरिद्म और एडेलमैन–पोमेरेन्स–रुमली टेस्ट सभी नम्बरों के लिए काम करते हैं, पर उत्तर पोलिनोमिअल टाइम में नहीं दे पाते। ये अल्गोरिद्म कभी भी गलत उत्तर नहीं देता है। मिल्लर-रेबिन टेस्ट और बेल्ली-पीएसडब्ल्यू टेस्ट तेज हैं और हर नंबर के लिए काम करते हैं, पर उनकी गलत उत्तर देने की कुछ सम्भावना होती है। "ये अल्गोरिद्म कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए किसी अप्रमाणित परिकल्पना की जरुरत नहीं है। मिल्लर टेस्ट तेज है, हर नंबर के लिए काम करता है, किसी भी परीक्षण में उसे गलत उत्तर देते नहीं पाया गया है; पर "वो कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए एक अप्रमाणित परिकल्पना जनरलाइज़ड रीमन्न परिकल्पना की जरुरत है। इन्हें भी देखें मिलर रैबिन नंबर अभाज्यता टेस्ट ग्रन्थ सूची Shoup Victor A computational introduction to number theory and algebra 2009 Cambridge University Press 9780521516440 2nd ed. http://shoup.net/ntb/ntb-v2.pdf 27 दिसंबर 2015 अंग्रेज़ी Chapter 21: Deterministic primality testing https://web.archive.org/web/20160203062547/http://shoup.net/ntb/ntb-v2.pdf 3 फ़रवरी 2016 dead श्रेणी:अल्गोरिद्म श्रेणी:कम्प्यूटर विज्ञान श्रेणी:संख्या सिद्धान्त