מבחן AKS לראשוניות

מבחן AKS לראשוניות הוא אלגוריתם דטרמיניסטי להוכחת ראשוניות שנוצר ופורסם על ידי מנינדרה אגרוול, ניראג' קיאל, וניטין סקסנה מהמכון ההודי לטכנולוגיה קנפור, ונקרא על שמם. האלגוריתם התפרסם ב-6 באוגוסט 2002, במאמרם "PRIMES is in P".^[1] החוקרים קיבלו שבחים רבים על עבודתם, כולל פרס גדל לשנת 2006 ופרס פולקרסון לשנת 2006. האלגוריתם קובע האם מספר הוא ראשוני או פריק בזמן ריצה פולינומי.

רקע מתמטי

אלגוריתם AKS מבוסס על המשפט המתמטי הבא: מספר טבעי n, גדול מ-2, הוא ראשוני, אם ורק אם מתקיימת הקונגרואנציה הבאה: $(x-a)^{n}\equiv (x^{n}-a){\pmod {n}}\qquad$ עבור כל המספרים הזרים ל-n (לא מחויב לכל פרמטר a). המשפט הוא הכללה לפולינומים של המשפט הקטן של פרמה, וניתן להוכיח אותו בעזרת הבינום של ניוטון עם התכונה של מקדם בינומי: ${n \choose k}\equiv 0{\pmod {n}}$ לכל k הקטן מ-n, אם ורק אם n הוא ראשוני.

האלגוריתם הוא כדלקמן:

קלט: מספר טבעי n > 1.
אם n = a^b למספרים שלמים a,b > 1, המספר פריק.
מצא r הקטן ביותר כך ש- $O_{r}(n)>(\log _{2}n)^{2}$ כאשר $O_{r}(n)$ הוא הסדר הכפלי של n מודולו r, כלומר: זהו המספר הטבעי הקטן ביותר k כך ש- $n^{k}\equiv 1{\pmod {r}}$ .
אם $1<\gcd(a,n)<n$ עבור איזשהו a ≤ r, המספר פריק.
בצע מ- a = 1 עד ל- $\scriptstyle \lfloor \scriptstyle {{\sqrt {\varphi (r)}}\log(n)}\scriptstyle \rfloor$ $\scriptstyle \lfloor \scriptstyle {{\sqrt {\varphi (r)}}\log(n)}\scriptstyle \rfloor$ (כאן $\varphi$ $\varphi$ היא פונקציית אוילר)
1. אם לא קיימים פולינומים f ו-g כך ש- $(X+a)^{n}-(X^{n}+a)=nf(x)+(x^{r}-1)g(x)$ עבור a (כלומר: $(X+a)^{n}\not \equiv (X^{n}+a){\pmod {(n,x^{r}-1)}}$ ), המספר פריק.
המספר ראשוני.