موضوع مقاله: آزمون اول بودن ای‌کی‌اس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # آزمون اول بودن ای‌کی‌اس | مقدمه: الگوریتم در زمان با پیچیدگی چندجمله‌ای می‌تواند تشخیص دهد که یک عدد اول یا مرکب است. | ## بخش 1: آزمون اول بودن ای‌کی‌اس | در سال ۲۰۰۶ نویسندگان به خاطر نگارش این مقاله موفق به کسب جایزه گودل و جایزه فالکرسون شدند. ویژگی‌های اصلی الگوریتم الگوریتم ای‌کی‌اس اولین الگوریتم تشخیص اول بودن اعداد است که به‌طور هم‌زمان خواص مهمی چون: عام بودن (قابلیت اجرا بر روی تمامی اعداد) ،پیچیدگی زمانی چندجمله‌ای، قطعی بودن (به این معنا که مطمانا الگوریتم اول بودن یا مرکب بودن را مشخص می‌کند)،نداشتن شرایط محدودکننده برای اجرای الگوریتم دارد. الگوریتم‌های موجود قبل از این الگوریتم حداکثر ۳ مورد از ۴ مورد ویژگی بالا را داشته‌اند. در زیر به معرفی کوتاه برخی از این ویژگی‌ها پرداخته‌ایم: • الگوریتم ای‌کی‌اس می‌تواند اول بودن یا مرکب بودن هر عددی را تشخیص دهد. بسیاری از آزمون‌های سریع تشخیص اعداد اول تنها برای اعدادی با ویژگی‌های خاص کار می‌کنند. • بیشینهٔ زمان اجرای الگوریتم را می‌توان به صورت چندجمله‌ای از تعداد ارقام عدد ورودی الگوریتم بیان کرد. آزمون‌های ECPP و APR می‌توانند به صورت قطعی نشان دهندکه عددی اول است یا خیر اما برای تمامی اعداد نمی‌توانند در پیچیدگی زمانی چندجمله‌ای (بر حسب تعداد ارقام ورودی) محاسبه شوند. • از دیگر ویژگی‌های الگوریتم ای‌کی‌اس این است که به صورت قطعی به این پرسش که آیا عدد ورودی اول است یا خیر پاسخ می‌دهد. این الگوریتم به‌طور کلی به اثبات رسیده‌است و به هیچ فرضیه یا حدسی وابسته نیست، برخلاف الگوریتم‌هایی همچون آزمون میلر که کاملاً قطعی و با پیچیدگی زمانی چندجمله‌ای برای تمامی ورودی‌ها است اما درستی این الگوریتم کاملاً وابسته به درستی حدس ریمان می‌باشد. مفاهیم اصلی پایهٔ آزمون ای‌کی‌اس بر مبنای قضیه زیر است: عدد طبیعیn اول می‌باشد اگر و تنها اگر معادله همنهشتی زیر به ازای تمامی اعداد a که نسبت به nاول می‌باشند، صادق باشد:(یا حتی برای برخی از اعداد صحیح نسبت به n اول، به خصوص برای a=۱) دقت کنید که در رابطهٔ بالا، x متغیر مستقل می‌باشد. | ## بخش 2: آزمون اول بودن ای‌کی‌اس | در واقع برای چک کردن درستی رابطهٔ بالا نمی‌توانیم به جای x عددگذاری کرده و درستی معادله را چک کنیم در عوض باید xرا به عنوان متغیر گرفته و عبارت سمت چپ را بر اساس آن بسط دهیم و ضرایب توان‌های متناظر x در دو طرف معادلهٔ همنشهتی را مقایسه کنیم. در واقع این قضیه تعمیمی از قضیهٔ کوچک فرما به چندجمله ای‌ها می‌باشد و به آسانی با استفاده از قضیه بسط دو جمله‌ای و خاصیت زیر از ضرایب بسط دو جمله‌ای اثبات می‌شود: برای هر k اگر و تنها اگر "n" عددی اول باشد. معادلهٔ (۱) که در بالا آورده‌ایم خود می‌تواند به عنوان آزمونی برای تشخیص اول بودن اعداد به کار رود اما مشکل آن در زمان اجرا است که از پیچیدگی زمانی نمایی می‌باشد. بنابراین برای کاهش پیچیدگی زمانی الگوریتم ای‌کی‌اس از معادلات همنهشتی زیر استفاده می‌کند: که معادل است با: که در آن f و g چندجمله‌ای‌های دلخواه می‌باشند. معادلهٔ همنهشتی بالا در زمان چندجمله‌ای بر حسب تعداد ارقام عدد n می‌تواند بررسی شود زیرا می‌توان ثابت کرد که کافی است r با n نسبت لگاریتمی داشته باشد. دقت کنید که تمامی اعداد اول در این معادله صدق می‌کنند (می‌توان در رابطهٔ (۳) به جای g چندجمله‌ای ثابت متحد با صفر را قرار داد و به رابطه (۱) رسید که برای n اول درست می‌باشد.) ولی بعضی از اعداد مرکب نیز در رابطهٔ (۳) صدق می‌کنند. نکتهٔ مهم در اثبات قضیه ای‌کی‌اس این است که به گونه‌ای عددی کوچک برای r و یک مجموعهٔ کوچک از اعداد طبیعی مثل A انتخاب می‌کند که اگر همنهشتی بالا برای r و تمامی aهای عضو A برقرار باشد انگاه n باید اول باشد. تاریخچه و زمان اجرا در نسخهٔ اولیهٔ مقالهٔ بالا، نویسندگان توانستند اثبات کنند که پیچیدگی زمانی الگوریتم Õ می‌باشد. به زبان دیگر الگوریتم بالا زمانی کمتر از لگاریتم تعداد ارقام ورودی به توان ۱۲ در یک عدد ثابت می‌باشد. اما این کران بالایی که در مقاله به دست آمده بود خیلی کران بالای مناسبی نبود، در واقع اگر حدس سوفی ژرمن در رابطه با توزیع اعداد اول را فرض کنیم آنگاه کران بالای داده شده را می‌توان تا Õ کاهش داد. | ## بخش 3: آزمون اول بودن ای‌کی‌اس | به علت وجود مدل‌های جدید از الگوریتم ای‌کی‌اس و به علت وجود برخی بازخوردها از الگوریتم، نسخهٔ جدیدی از “Pimes is in P” با صورت‌بندی جدید از الگوریتم و اثباتی جدید از الگوریتم منتشر شد. در نسخهٔ جدید ایدهٔ کلی الگوریتم بدون تغییر باقی ماند و تغییر در نحوهٔ انتخاب r بوده و همچنین اثبات منسجم تری برای الگوریتم ارائه شد. اثبات قبلی الگوریتم از بر پایهٔ روش‌های متفاوتی بوده در اثبات جدید ایدهٔ اصلی که تقریباً تمامی کاراثبات را انجام می‌دهد بر پایه استفاده از چندجمله ای‌های دایره بر روی میدان‌های متناهی می‌باشد. اما تحلیل‌هایی که هندریک لنسترا و کارل پامرنس بر روی این حدس انجام داده‌اند نشان می‌دهد که به احتمال زیاد این حدس اشتباه می‌باشد. اگر n عددی اول باشد آنگاه الگوریتم همواره n را به عنوان عدد اول بر میگرداند چرا که در این صورت هیچ گاه مراحل ۱ یا ۳ از الگوریتم مقدار مرکب برای n چاپ نمی‌کنند. همچنین مرحلهٔ ۵ نیز هیچ گاه n را به عنوان عدد مرکب چاپ نمی‌کند زیرا رابطهٔ (۲) برای تمامی اعداد اول صادق است. بنابراین الگوریتم در یکی از مراحل ۴ یا ۶ عدد ورودی را به عنوان عددی اول برمیگرداند. برعکس، اگر که n عددی مرکب باشد آنگاه الگوریتم همواره آن را به عنوان عدد مرکب بر میگرداند: اگر چنانچه الگوریتم n را به عنوان عددی اول چاپ کند این عمل در یکی از مراحل ۴ یا ۶ رخ داده‌است. حالت دیگری که می‌ماند این است که الگوریتم در مرحلهٔ ۶ عدد n را به عنوان اول چاپ کند. | ## جمع‌بندی | در مقاله‌ای که منتشر شده‌است اثبات شده‌است که شرایط اعمال شده در ۵ برای اینکه مطمان باشیم که n عددی مرکب است کافی می‌باشد.