برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: الگوریتم ای‌کی‌اس اولین الگوریتم تشخیص اول بودن اعداد است که به‌طور هم‌زمان خواص مهمی چون: عام بودن (قابلیت اجرا بر روی تمامی اعداد)، پیچیدگی زمانی چندجمله‌ای، قطعی بودن (به این معنا که مطمانا الگوریتم اول بودن یا مرکب بودن را مشخص می‌کند)، نداشتن شرایط محدودکننده برای اجرای الگوریتم دارد. الگوریتم‌های موجود قبل از این الگوریتم حداکثر ۳ مورد از ۴ مورد ویژگی بالا را داشته‌اند. در زیر به معرفی کوتاه برخی از این ویژگی‌ها پرداخته‌ایم: پایه آزمون ای‌کی‌اس بر مبنای قضیه زیر است: دقت کنید که در رابطه بالا، x متغیر مستقل می‌باشد. در واقع برای چک کردن درستی رابطه بالا نمی‌توانیم به جای x عددگذاری کرده و درستی معادله را چک کنیم در عوض باید xرا به عنوان متغیر گرفته و عبارت سمت چپ را بر اساس آن بسط دهیم و ضرایب توان‌های متناظر x در دو طرف معادله همنشهتی را مقایسه کنیم. در واقع این قضیه تعمیمی از قضیه کوچک فرما به چندجمله ای‌ها می‌باشد و به آسانی با استفاده از قضیه بسط دو جمله‌ای و خاصیت زیر از ضرایب بسط دو جمله‌ای اثبات می‌شود: معادله (۱) که در بالا آورده‌ایم خود می‌تواند به عنوان آزمونی برای تشخیص اول بودن اعداد به کار رود اما مشکل آن در زمان اجرا است که از پیچیدگی زمانی نمایی می‌باشد. بنابراین برای کاهش پیچیدگی زمانی الگوریتم ای‌کی‌اس از معادلات همنهشتی زیر استفاده می‌کند: که معادل است با: که در آن f و g چندجمله‌ای‌های دلخواه می‌باشند. معادله همنهشتی بالا در زمان چندجمله‌ای بر حسب تعداد ارقام عدد n می‌تواند بررسی شود زیرا می‌توان ثابت کرد که کافی است r با n نسبت لگاریتمی داشته باشد. دقت کنید که تمامی اعداد اول در این معادله صدق می‌کنند (می‌توان در رابطه (۳) به جای g چندجمله‌ای ثابت متحد با صفر را قرار داد و به رابطه (۱) رسید که برای n اول درست می‌باشد.) ولی بعضی از اعداد مرکب نیز در رابطه (۳) صدق می‌کنند. نکته مهم در اثبات قضیه ای‌کی‌اس این است که به گونه‌ای عددی کوچک برای r و یک مجموعه کوچک از اعداد طبیعی مثل a انتخاب می‌کند که اگر همنهشتی بالا برای r و تمامی aهای عضو a برقرار باشد انگاه n باید اول باشد. در نسخه اولیه مقاله بالا، نویسندگان توانستند اثبات کنند که پیچیدگی زمانی الگوریتم õ می‌باشد. به زبان دیگر الگوریتم بالا زمانی کمتر از لگاریتم تعداد ارقام ورودی به توان ۱۲ در یک عدد …
برداشت:
آزمون اول بودن aks (که همچنین به نام‌های آزمون اول بودن agrawal-kayal-saxena و آزمون دایره بری aks شناخته می‌شود) یک الگوریتم قطعی برای اثبات اول بودن یا نبودن اعداد طبیعی می‌باشد که توسط مانیندرا آرگاوال ، نیراج کایال و نیتین ساکسنا –پژوهشگران علوم رایانه در موسسه هندی فناوری کانپور- در تاریخ ۶ اوت ۲۰۰۲ در مقاله‌ای با عنوان « prime is in p » منتشر شد . الگوریتم در زمان با پیچیدگی چندجمله‌ای می‌تواند تشخیص دهد که یک عدد اول یا مرکب است . در سال ۲۰۰۶ نویسندگان به خاطر نگارش این مقاله موفق به کسب جایزه گودل و جایزه فالکرسون شدند .