آزمون اول بودن ای‌کی‌اس

آزمون اول بودن AKS (که همچنین به نام‌های آزمون اول بودن Agrawal-Kayal-Saxena و آزمون دایره بری AKS شناخته می‌شود) یک الگوریتم قطعی برای اثبات اول بودن یا نبودن اعداد طبیعی می‌باشد که توسط مانیندرا آرگاوال، نیراج کایال و نیتین ساکسنا –پژوهشگران علوم رایانه در موسسه هندی فناوری کانپور- در تاریخ ۶ اوت ۲۰۰۲ در مقاله‌ای با عنوان“prime is in P” منتشر شد. الگوریتم در زمان با پیچیدگی چندجمله‌ای می‌تواند تشخیص دهد که یک عدد اول یا مرکب است. در سال ۲۰۰۶ نویسندگان به خاطر نگارش این مقاله موفق به کسب جایزه گودل و جایزه فالکرسون شدند.

ویژگی‌های اصلی الگوریتم

الگوریتم ای‌کی‌اس اولین الگوریتم تشخیص اول بودن اعداد است که به‌طور هم‌زمان خواص مهمی چون: عام بودن (قابلیت اجرا بر روی تمامی اعداد) ،پیچیدگی زمانی چندجمله‌ای، قطعی بودن (به این معنا که مطمانا الگوریتم اول بودن یا مرکب بودن را مشخص می‌کند)،نداشتن شرایط محدودکننده برای اجرای الگوریتم دارد. الگوریتم‌های موجود قبل از این الگوریتم حداکثر ۳ مورد از ۴ مورد ویژگی بالا را داشته‌اند. در زیر به معرفی کوتاه برخی از این ویژگی‌ها پرداخته‌ایم:

• الگوریتم ای‌کی‌اس می‌تواند اول بودن یا مرکب بودن هر عددی را تشخیص دهد. بسیاری از آزمون‌های سریع تشخیص اعداد اول تنها برای اعدادی با ویژگی‌های خاص کار می‌کنند. برای مثال آزمون Lucas-Lehmer تنها برای اعداد مرسن و آزمون Pepin تنها برای اعداد فرما کار می‌کنند.

• بیشینهٔ زمان اجرای الگوریتم را می‌توان به صورت چندجمله‌ای از تعداد ارقام عدد ورودی الگوریتم بیان کرد. آزمون‌های ECPP و APR می‌توانند به صورت قطعی نشان دهندکه عددی اول است یا خیر اما برای تمامی اعداد نمی‌توانند در پیچیدگی زمانی چندجمله‌ای (بر حسب تعداد ارقام ورودی) محاسبه شوند.

• از دیگر ویژگی‌های الگوریتم ای‌کی‌اس این است که به صورت قطعی به این پرسش که آیا عدد ورودی اول است یا خیر پاسخ می‌دهد. الگوریتم‌هایی تصادفی همچون Miller-Rabin و Ballie-PSW با اینکه در زمان چندجمله‌ای اجرا می‌شوند تنها جوابی احتمالی به صورت خروجی ارائه می‌دهند.

• همانطور که گفته شد الگوریتم ای‌کی‌اس وابسته به شرایط خاصی نمی‌باشد. این الگوریتم به‌طور کلی به اثبات رسیده‌است و به هیچ فرضیه یا حدسی وابسته نیست، برخلاف الگوریتم‌هایی همچون آزمون میلر که کاملاً قطعی و با پیچیدگی زمانی چندجمله‌ای برای تمامی ورودی‌ها است اما درستی این الگوریتم کاملاً وابسته به درستی حدس ریمان می‌باشد.

مفاهیم اصلی

پایهٔ آزمون ای‌کی‌اس بر مبنای قضیه زیر است:

عدد طبیعیn اول می‌باشد اگر و تنها اگر معادله همنهشتی زیر به ازای تمامی اعداد a که نسبت به nاول می‌باشند، صادق باشد:(یا حتی برای برخی از اعداد صحیح نسبت به n اول، به خصوص برای a=۱)

$(x-a)^{n}\equiv (x^{n}-a){\pmod {n}}\qquad (1)$

دقت کنید که در رابطهٔ بالا، x متغیر مستقل می‌باشد. در واقع برای چک کردن درستی رابطهٔ بالا نمی‌توانیم به جای x عددگذاری کرده و درستی معادله را چک کنیم در عوض باید xرا به عنوان متغیر گرفته و عبارت سمت چپ را بر اساس آن بسط دهیم و ضرایب توان‌های متناظر x در دو طرف معادلهٔ همنشهتی را مقایسه کنیم. در واقع این قضیه تعمیمی از قضیهٔ کوچک فرما به چندجمله ای‌ها می‌باشد و به آسانی با استفاده از قضیه بسط دو جمله‌ای و خاصیت زیر از ضرایب بسط دو جمله‌ای اثبات می‌شود:

${n \choose k}\equiv 0{\pmod {n}}$ برای هر k $0<k<n$ اگر و تنها اگر "n" عددی اول باشد.

معادلهٔ (۱) که در بالا آورده‌ایم خود می‌تواند به عنوان آزمونی برای تشخیص اول بودن اعداد به کار رود اما مشکل آن در زمان اجرا است که از پیچیدگی زمانی نمایی می‌باشد. بنابراین برای کاهش پیچیدگی زمانی الگوریتم ای‌کی‌اس از معادلات همنهشتی زیر استفاده می‌کند:

$(x-a)^{n}\equiv (x^{n}-a){\pmod {(n,x^{r}-1)}}\qquad (2)$

که معادل است با:

$(x-a)^{n}-(x^{n}-a)=nf+(x^{r}-1)g\qquad (3)$

که در آن f و g چندجمله‌ای‌های دلخواه می‌باشند. معادلهٔ همنهشتی بالا در زمان چندجمله‌ای بر حسب تعداد ارقام عدد n می‌تواند بررسی شود زیرا می‌توان ثابت کرد که کافی است r با n نسبت لگاریتمی داشته باشد. دقت کنید که تمامی اعداد اول در این معادله صدق می‌کنند (می‌توان در رابطهٔ (۳) به جای g چندجمله‌ای ثابت متحد با صفر را قرار داد و به رابطه (۱) رسید که برای n اول درست می‌باشد.) ولی بعضی از اعداد مرکب نیز در رابطهٔ (۳) صدق می‌کنند. نکتهٔ مهم در اثبات قضیه ای‌کی‌اس این است که به گونه‌ای عددی کوچک برای r و یک مجموعهٔ کوچک از اعداد طبیعی مثل A انتخاب می‌کند که اگر همنهشتی بالا برای r و تمامی aهای عضو A برقرار باشد انگاه n باید اول باشد.

تاریخچه و زمان اجرا

در نسخهٔ اولیهٔ مقالهٔ بالا، نویسندگان توانستند اثبات کنند که پیچیدگی زمانی الگوریتم Õ$(\log ^{12}(n))$ می‌باشد.

به زبان دیگر الگوریتم بالا زمانی کمتر از لگاریتم تعداد ارقام ورودی به توان ۱۲ در یک عدد ثابت می‌باشد. اما این کران بالایی که در مقاله به دست آمده بود خیلی کران بالای مناسبی نبود، در واقع اگر حدس سوفی ژرمن در رابطه با توزیع اعداد اول را فرض کنیم آنگاه کران بالای داده شده را می‌توان تا Õ$(\log ^{6}(n))$ کاهش داد.

طی چند ماه پس از انتشار مقالهٔ فوق چندین مدل دیگر برای این الگوریتم داده شد که سرعت اجرای الگوریتم را از نظر اندازهٔ ضریب ثابت بهبود بخشید (نه از لحاظ مرتبهٔ زمانی). با توجه به وجود مدل‌های فراوان از الگوریتم AKS، Crandall و Papadopoulos در مقالهٔ خود با عنوان «در باب اجرای آزمون‌های اول بودن رده ای‌کی‌اس» که در مارس سال ۲۰۰۳ منتشر شد از الگوریتم‌های بالا با عنوان «کلاس ای‌کی‌اس» استفاده کرده‌اند.

به علت وجود مدل‌های جدید از الگوریتم ای‌کی‌اس و به علت وجود برخی بازخوردها از الگوریتم، نسخهٔ جدیدی از “Pimes is in P” با صورت‌بندی جدید از الگوریتم و اثباتی جدید از الگوریتم منتشر شد. (این نسخهٔ جدید در «سال‌نگاشت ریاضیات» منتشر شده‌است). در نسخهٔ جدید ایدهٔ کلی الگوریتم بدون تغییر باقی ماند و تغییر در نحوهٔ انتخاب r بوده و همچنین اثبات منسجم تری برای الگوریتم ارائه شد. اثبات قبلی الگوریتم از بر پایهٔ روش‌های متفاوتی بوده در اثبات جدید ایدهٔ اصلی که تقریباً تمامی کاراثبات را انجام می‌دهد بر پایه استفاده از چندجمله ای‌های دایره بر روی میدان‌های متناهی می‌باشد. همچنین در نسخهٔ جدید کران بالای الگوریتم به Õ$(\log ^{10.5}(n))$ کاهش یافت. با استفاده از نتایجی از قضیهٔ sieve می‌توان این الگوریتم را حتی تا Õ$(\log ^{7.5}(n))$ کاهش داد.

در سال ۲۰۰۵ Carl Pomerance و H.W.Lenstra,JR موفق شدند با ارایهٔ مدل جدیدی از الگوریتم AKS مرتبهٔ زمانی اجرای الگوریتم را تا Õ(log^۶(n)) کاهش دهند.

همچنین Agarwal,Kayalو Saxena مدلی جدید از الگوریتم را پیشنهاد دادند که دارای مرتبهٔ زمانی Õ$(\log ^{3}(n))$ می‌باشد که بر پایهٔ حدسی از Bhattacharjee و Pandey که در سال 2002 بیان شد مبتنی است. اما تحلیل‌هایی که هندریک لنسترا و کارل پامرنس بر روی این حدس انجام داده‌اند نشان می‌دهد که به احتمال زیاد این حدس اشتباه می‌باشد.

الگوریتم

۰-عدد n>۱ را به عنوان ورودی وارد کن.

۱-اگر به ازای a>۱و b>۱ ای طبیعی داشته باشیم n=a^b انگاه چاپ کنn مرکب است.

۲-کوچک‌ترین عدد r را بیابید که o_r (n)>〖(log⁡〖n)〗〗^۲

۳-اگر ۱<gcd⁡〖(a,n)<n〗 برای a≤r اتفاق بیفتد آنگاه چائ کنn مرکب است.

۴-اگر که n≤r انگاه چاپ کن که n اول است.

۵-اگر برای هر a از ۱ تا ⌊log⁡〖n*〗 √(φ(r))┤

داشتیم 〖(x+a)〗^n≠x^n+a (mod x^r-۱،n)انگاه چاپ کن n مرکب است.

۶-چاپ کن که n اول است.

در اینجا نماد ‎o_r(n)‏ مرتبهٔ n به پیمانهٔ r می‌باشد. همچنین لگاریتم استفاده شده در پایهٔ ۲ می‌باشد و $\scriptstyle \varphi (r)$ تابع فی اویلر می‌باشد. اگر n عددی اول باشد آنگاه الگوریتم همواره n را به عنوان عدد اول بر میگرداند چرا که در این صورت هیچ گاه مراحل ۱ یا ۳ از الگوریتم مقدار مرکب برای n چاپ نمی‌کنند. همچنین مرحلهٔ ۵ نیز هیچ گاه n را به عنوان عدد مرکب چاپ نمی‌کند زیرا رابطهٔ (۲) برای تمامی اعداد اول صادق است. بنابراین الگوریتم در یکی از مراحل ۴ یا ۶ عدد ورودی را به عنوان عددی اول برمیگرداند. برعکس، اگر که n عددی مرکب باشد آنگاه الگوریتم همواره آن را به عنوان عدد مرکب بر میگرداند: اگر چنانچه الگوریتم n را به عنوان عددی اول چاپ کند این عمل در یکی از مراحل ۴ یا ۶ رخ داده‌است. در حالت اول داریم n≤r که نتیجه می‌دهد n عاملی همچون a دارد که a≤r و ۱<gcd⁡(a,n)<n که در اینصورت باید مرکب برگرداند. حالت دیگری که می‌ماند این است که الگوریتم در مرحلهٔ ۶ عدد n را به عنوان اول چاپ کند. در مقاله‌ای که منتشر شده‌است اثبات شده‌است که شرایط اعمال شده در ۵ برای اینکه مطمان باشیم که n عددی مرکب است کافی می‌باشد.