آزمون اول بودن ای‌کی‌اس کیست؟ توضیح بده.
آزمون اول بودن 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&gt;۱ را به عنوان ورودی وارد کن.۱-اگر به ازای a&gt;۱و b&gt;۱ ای طبیعی داشته باشیم n=a^b انگاه چاپ کنn مرکب است.۲-کوچک‌ترین عدد r را بیابید که o_r (n)&gt;〖(log⁡〖n)〗〗^۲۳-اگر ۱&lt;gcd⁡〖(a,n)&lt;n〗 برای a≤r اتفاق بیفتد آنگاه چائ کنn مرکب است.۴-اگر که n≤r انگاه چاپ کن که n اول است.۵-اگر برای هر a از ۱ تا ⌊log⁡〖n*〗 √(φ(r))┤۶-چاپ کن که n اول است.در اینجا نماد "o""r"("n") مرتبهٔ n به پیمانهٔ r می‌باشد. همچنین لگاریتم استفاده شده در پایهٔ ۲ می‌باشد و formula_11 تابع فی اویلر می‌باشد.اگر n عددی اول باشد آنگاه الگوریتم همواره n را به عنوان عدد اول بر میگرداند چرا که در این صورت هیچ گاه مراحل ۱ یا ۳ از الگوریتم مقدار مرکب برای n چاپ نمی‌کنند. همچنین مرحلهٔ ۵ نیز هیچ گاه n را به عنوان عدد مرکب چاپ نمی‌کند زیرا رابطهٔ (۲) برای تمامی اعداد اول صادق است. بنابراین الگوریتم در یکی از مراحل ۴ یا ۶ عدد ورودی را به عنوان عددی اول برمیگرداند.برعکس، اگر که n عددی مرکب باشد آنگاه الگوریتم همواره آن را به عنوان عدد مرکب بر میگرداند: اگر چنانچه الگوریتم n را به عنوان عددی اول چاپ کند این عمل در یکی از مراحل ۴ یا ۶ رخ داده‌است. در حالت اول داریم n≤r که نتیجه می‌دهد n عاملی همچون a دارد که a≤r و ۱&lt;gcd⁡(a,n)&lt;n که در اینصورت باید مرکب برگرداند.حالت دیگری که می‌ماند این است که الگوریتم در مرحلهٔ ۶ عدد n را به عنوان اول چاپ کند. در مقاله‌ای که منتشر شده‌است اثبات شده‌است که شرایط اعمال شده در ۵ برای اینکه مطمان باشیم که n عددی مرکب است کافی می‌باشد.