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

{{Dablink|इस लेख में सुधार किया जा रहा है। इसकी भाषा को सरल बना दी जाएगा, और सन्दर्भ भी जोड़ दिए जाएंगे। थोड़ा समय दीजिए।}}

'''ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट''' पहला ''पोलीनोमिअल टाइम'' है [[अल्गोरिद्म]] (कंप्यूटर विज्ञान में पोलीनोमिअल टाइम अल्गोरिद्मों को तेज माना जाता है<ref name = arora_barak_polynomial>{{harvtxt|Arora|Barak|2009|loc = 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."}}</ref><ref name="papadimitriou">{{पुस्तक सन्दर्भ|last1=Papadimitriou|first1=Christos H.|title=Computational complexity|url=https://archive.org/details/computationalcom00papa|date=1994|publisher=Addison-Wesley|location=Reading, Mass. [u.a.]|isbn=0-201-53082-1|pages=[https://archive.org/details/computationalcom00papa/page/n18 6]|edition=Reprinted with corr., [Nachdr.]|language=अंग्रेज़ी|quote=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.}}</ref><ref>{{पुस्तक सन्दर्भ|last1=Cormen|first1=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|title=Introduction to algorithms|url=https://archive.org/details/introductiontoal00corm_805|chapter=Polynomial time|date=2009|publisher=MIT Press|location=Cambridge, Massachusetts|isbn=978-0-262-03384-8|pages=[https://archive.org/details/introductiontoal00corm_805/page/n1073 1053]-1054|edition=3rd ed.|language=अंग्रेज़ी}}</ref>) जो बताता है कि कोई नंबर [[अभाज्य संख्या|अभाज्य]] है या नहीं।<ref name=mathworld>{{वेब सन्दर्भ|title=AKS Primality Test|url=http://mathworld.wolfram.com/AKSPrimalityTest.html|website=MathWorld|publisher=Wolfram|accessdate=26 दिसंबर 2015|language=अंग्रेज़ी|archive-url=https://web.archive.org/web/20151227154947/http://mathworld.wolfram.com/AKSPrimalityTest.html|archive-date=27 दिसंबर 2015|url-status=live}}</ref> इसका आविष्कार 2002 में [[भारतीय प्रौद्योगिकी संस्थान कानपुर]] के तीन कंप्यूटर वैज्ञानिकों – [[मणीन्द्र अग्रवाल]], [[नीरज कयाल]] और [[नितिन सक्सेना]] ने किया था।<ref name=NYT>{{समाचार सन्दर्भ|last1=Robinson|first1=Sara|title=New Method Said to Solve Key Problem in Math|url=http://www.nytimes.com/2002/08/08/science/08MATH.html|accessdate=26 दिसंबर 2015|language=अंग्रेज़ी|work=New York Times|date=8 अगस्त 2002|archive-url=https://web.archive.org/web/20151227150006/http://www.nytimes.com/2002/08/08/science/08MATH.html|archive-date=27 दिसंबर 2015|url-status=live}}</ref><ref name=AMS_notices>{{जर्नल सन्दर्भ|last1=Bornemann|first1=Folkmar|title=PRIMES Is in P: A Breakthrough for "Everyman"|journal=Notices of the AMS|date=2003|volume=50|issue=5|pages=545-552|url=http://www.ams.org/journals/notices/200305/fea-bornemann.pdf|accessdate=26 दिसंबर 2015|language=अंग्रेज़ी|publisher=American Mathematical Society|archive-url=https://web.archive.org/web/20151227150000/http://www.ams.org/journals/notices/200305/fea-bornemann.pdf|archive-date=27 दिसंबर 2015|url-status=live}}</ref>

किसी भी अल्गोरिद्म के लिए चार आवश्यकताएँ होती है: 1) वो हर इनपुट के लिए आउटपुट देता हो, 2) वो जल्दी उत्तर देता हो (more precisely: वो पोलीनोमिअल टाइम में उत्तर देता हो), 3) वो कभी गलत उत्तर न देता हो और 4) वो किसी अप्रमाणित परिकल्पना पर निर्भर न करता हो। नंबर की अभाज्यता जांचने के लिए इस से पहले के सभी अल्गोरिद्म इन चार में से अधिक से अधिक तीन आवश्यकताओं को पूर्ण करते थे। ये पहला अल्गोरिद्म है जो इन चारों आवश्यकताओं को पूर्ण करता है।
# इस अल्गोरिद्म का प्रयोग किसी भी नंबर भी अभाज्यता जानने के लिए किया जा सकता है। इस से पहले के कई अल्गोरिद्म केवल खास श्रेणियों के नम्बरों के लिए काम करते हैं। उदाहरण के लिए ''लुकास-लेहमर टेस्ट'' सिर्फ ''मर्सेन नम्बरों'' के लिए काम करता है, और ''पेपिन टेस्ट'' सिर्फ ''फर्मेट नम्बरों'' के लिए। 
# ये अल्गोरिद्म पोलिनोमिअल टाइम में उत्तर देता है। सरल भाषा में कहें तो ये कम समय में उत्तर दे देता है। इस से पहले ऐसे अल्गोरिद्म थे जो हर नंबर के लिए काम करते थे, पर पोलिनोमिअल टाइम में उत्तर नहीं देते थे। ऐसे अल्गोरिद्मों को 60 डिजिट के कुछ नम्बरों की अभाज्यता जांचने के लिए खरबों वर्ष लगेंगे, जो कि ब्रह्माण्ड की वर्तमान उम्र 13.82 अरब वर्ष से 100 गुणा है। ''अंडाकार वक्र'' पर आधारित अल्गोरिद्म और ''एडेलमैन–पोमेरेन्स–रुमली टेस्ट'' सभी नम्बरों के लिए काम करते हैं, पर उत्तर पोलिनोमिअल टाइम में नहीं दे पाते। 
# ये अल्गोरिद्म कभी भी गलत उत्तर नहीं देता है। ''मिल्लर-रेबिन टेस्ट'' और ''बेल्ली-पीएसडब्ल्यू टेस्ट'' तेज हैं और हर नंबर के लिए काम करते हैं, पर उनकी गलत उत्तर देने की कुछ सम्भावना होती है। 
# "ये अल्गोरिद्म कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए किसी अप्रमाणित परिकल्पना की जरुरत नहीं है। ''मिल्लर टेस्ट'' तेज है, हर नंबर के लिए काम करता है, किसी भी परीक्षण में उसे गलत उत्तर देते नहीं पाया गया है; पर "वो कभी गलत उत्तर नहीं देता है", यह साबित करने के लिए एक अप्रमाणित परिकल्पना ''जनरलाइज़ड रीमन्न परिकल्पना'' की जरुरत है।
== इन्हें भी देखें ==
* [[मिल्लर रैबिन नंबर अभाज्यता टेस्ट|मिलर रैबिन नंबर अभाज्यता टेस्ट]]
{{सन्दर्भो}}
==ग्रन्थ सूची==
* {{पुस्तक सन्दर्भ|last1=Shoup|first1=Victor|title=A computational introduction to number theory and algebra|date=2009|publisher=Cambridge University Press|isbn=9780521516440|edition=2nd ed.|url=http://shoup.net/ntb/ntb-v2.pdf|accessdate=27 दिसंबर 2015|language=अंग्रेज़ी|chapter=Chapter 21: Deterministic primality testing|archive-url=https://web.archive.org/web/20160203062547/http://shoup.net/ntb/ntb-v2.pdf|archive-date=3 फ़रवरी 2016|url-status=dead}}

[[श्रेणी:अल्गोरिद्म]]
[[श्रेणी:कम्प्यूटर विज्ञान]]
[[श्रेणी:संख्या सिद्धान्त]]