آزمون اول بودن ای‌کی‌اس
آزمون اول بودن AKS (که همچنین به نام‌های آزمون اول بودن Agrawal-Kayal-Saxena و آزمون دایره بری AKS شناخته می‌شود) یک الگوریتم قطعی برای اثبات اول بودن یا نبودن اعداد طبیعی می‌باشد که توسط مانیندرا آرگاوال، نیراج کایال و نیتین ساکسنا –پژوهشگران علوم رایانه در موسسه هندی فناوری کانپور- در تاریخ ۶ اوت ۲۰۰۲ در مقاله‌ای با عنوان“prime is in P” منتشر شد. الگوریتم در زمان با پیچیدگی چندجمله‌ای می‌تواند تشخیص دهد که یک عدد اول یا مرکب است. در سال ۲۰۰۶ نویسندگان به خاطر نگارش این مقاله موفق به کسب جایزه گودل و جایزه فالکرسون شدند.
الگوریتم ای‌کی‌اس اولین الگوریتم تشخیص اول بودن اعداد است که به‌طور هم‌زمان خواص مهمی چون: عام بودن (قابلیت اجرا بر روی تمامی اعداد) ،پیچیدگی زمانی چندجمله‌ای، قطعی بودن (به این معنا که مطمانا الگوریتم اول بودن یا مرکب بودن را مشخص می‌کند)،نداشتن شرایط محدودکننده برای اجرای الگوریتم دارد. الگوریتم‌های موجود قبل از این الگوریتم حداکثر ۳ مورد از ۴ مورد ویژگی بالا را داشته‌اند. در زیر به معرفی کوتاه برخی از این ویژگی‌ها پرداخته‌ایم:
پایهٔ آزمون ای‌کی‌اس بر مبنای قضیه زیر است:
دقت کنید که در رابطهٔ بالا، x متغیر مستقل می‌باشد. در واقع برای چک کردن درستی رابطهٔ بالا نمی‌توانیم به جای x عددگذاری کرده و درستی معادله را چک کنیم در عوض باید xرا به عنوان متغیر گرفته و عبارت سمت چپ را بر اساس آن بسط دهیم و ضرایب توان‌های متناظر x در دو طرف معادلهٔ همنشهتی را مقایسه کنیم. در واقع این قضیه تعمیمی از قضیهٔ کوچک فرما به چندجمله ای‌ها می‌باشد و به آسانی با استفاده از قضیه بسط دو جمله‌ای و خاصیت زیر از ضرایب بسط دو جمله‌ای اثبات می‌شود:
معادلهٔ (۱) که در بالا آورده‌ایم خود می‌تواند به عنوان آزمونی برای تشخیص اول بودن اعداد به کار رود اما مشکل آن در زمان اجرا است که از پیچیدگی زمانی نمایی می‌باشد. بنابراین برای کاهش پیچیدگی زمانی الگوریتم ای‌کی‌اس از معادلات همنهشتی زیر استفاده می‌کند:
که معادل است با:
که در آن f و g چندجمله‌ای‌های دلخواه می‌باشند. معادلهٔ همنهشتی بالا در زمان چندجمله‌ای بر حسب تعداد ارقام عدد n می‌تواند بررسی شود زیرا می‌توان ثابت کرد که کافی است r با n نسبت لگاریتمی داشته باشد. دقت کنید که تمامی اعداد اول در این معادله صدق می‌کنند (می‌توان در رابطهٔ (۳) به جای g چندجمله‌ای ثابت متحد با صفر را قرار داد و به رابطه (۱) رسید که برای n اول درست می‌باشد.) ولی بعضی از اعداد مرکب نیز در رابطهٔ (۳) صدق می‌کنند. نکتهٔ مهم در اثبات قضیه ای‌کی‌اس این است که به گونه‌ای عددی کوچک برای r و یک مجموعهٔ کوچک از اعداد طبیعی مثل A انتخاب می‌کند که اگر همنهشتی بالا برای r و تمامی aهای عضو A برقرار باشد انگاه n باید اول باشد.
در نسخهٔ اولیهٔ مقالهٔ بالا، نویسندگان توانستند اثبات کنند که پیچیدگی زمانی الگوریتم Õformula_6 می‌باشد.
به زبان دیگر الگوریتم بالا زمانی کمتر از لگاریتم تعداد ارقام ورودی به توان ۱۲ در یک عدد ثابت می‌باشد. اما این کران بالایی که در مقاله به دست آمده بود خیلی کران بالای مناسبی نبود، در واقع اگر حدس سوفی ژرمن در رابطه با توزیع اعداد اول را فرض کنیم آنگاه کران بالای داده شده را می‌توان تا Õformula_7 کاهش داد.
طی چند ماه پس از انتشار مقالهٔ فوق چندین مدل دیگر برای این الگوریتم داده شد که سرعت اجرای الگوریتم را از نظر اندازهٔ ضریب ثابت بهبود بخشید (نه از لحاظ مرتبهٔ زمانی). با توجه به وجود مدل‌های فراوان از الگوریتم AKS، Crandall و Papadopoulos در مقالهٔ خود با عنوان «در باب اجرای آزمون‌های اول بودن رده ای‌کی‌اس» که در مارس سال ۲۰۰۳ منتشر شد از الگوریتم‌های بالا با عنوان «کلاس ای‌کی‌اس» استفاده کرده‌اند.
به علت وجود مدل‌های جدید از الگوریتم ای‌کی‌اس و به علت وجود برخی بازخوردها از الگوریتم، نسخهٔ جدیدی از “Pimes is in P” با صورت‌بندی جدید از الگوریتم و اثباتی جدید از الگوریتم منتشر شد. (این نسخهٔ جدید در «سال‌نگاشت ریاضیات» منتشر شده‌است). در نسخهٔ جدید ایدهٔ کلی الگوریتم بدون تغییر باقی ماند و تغییر در نحوهٔ انتخاب r بوده و همچنین اثبات منسجم تری برای الگوریتم ارائه شد. اثبات قبلی الگوریتم از بر پایهٔ روش‌های متفاوتی بوده در اثبات جدید ایدهٔ اصلی که تقریباً تمامی کاراثبات را انجام می‌دهد بر پایه استفاده از چندجمله ای‌های دایره بر روی میدان‌های متناهی می‌باشد. همچنین در نسخهٔ جدید کران بالای الگوریتم به Õformula_8 کاهش یافت. با استفاده از نتایجی از قضیهٔ sieve می‌توان این الگوریتم را حتی تا Õformula_9 کاهش داد.
در سال ۲۰۰۵ Carl Pomerance و H.W.Lenstra,JR موفق شدند با ارایهٔ مدل جدیدی از الگوریتم AKS مرتبهٔ زمانی اجرای الگوریتم را تا Õ(log("n")) کاهش دهند.
همچنین Agarwal,Kayalو Saxena مدلی جدید از الگوریتم را پیشنهاد دادند که دارای مرتبهٔ زمانی Õformula_10 می‌باشد که بر پایهٔ حدسی از Bhattacharjee و Pandey که در سال 2002 بیان شد مبتنی است. اما تحلیل‌هایی که هندریک لنسترا و کارل پامرنس بر روی این حدس انجام داده‌اند نشان می‌دهد که به احتمال زیاد این حدس اشتباه می‌باشد.
۰-عدد n>۱ را به عنوان ورودی وارد کن.
۱-اگر به ازای a>۱و b>۱ ای طبیعی داشته باشیم n=a^b انگاه چاپ کنn مرکب است.
۲-کوچک‌ترین عدد r را بیابید که o_r (n)>〖(log⁡〖n)〗〗^۲
۳-اگر ۱