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

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

רקע מתמטי

אלגוריתם AKS מבוסס על המשפט המתמטי הבא: מספר טבעי n, גדול מ-2, הוא ראשוני, אם ורק אם מתקיימת הקונגרואנציה הבאה: $(x-a)^{n}\equiv (x^{n}-a){\pmod {n}}\qquad$ עבור כל המספרים הזרים ל-n (לא מחויב לכל פרמטר a). המשפט הוא הכללה לפולינומים של המשפט הקטן של פרמה, וניתן להוכיח אותו בעזרת הבינום של ניוטון עם התכונה של מקדם בינומי: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n \choose k} \equiv 0 \pmod{n}} לכל k הקטן מ-n, אם ורק אם n הוא ראשוני.

האלגוריתם

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

1. קלט: מספר טבעי n > 1.
2. אם n = a^b למספרים שלמים a,b > 1, המספר פריק.
3. מצא r הקטן ביותר כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O_r(n) > ( \log_2 n )^2} כאשר $O_{r}(n)$ הוא הסדר הכפלי של n מודולו r, כלומר: זהו המספר הטבעי הקטן ביותר k כך ש-$n^{k}\equiv 1{\pmod {r}}$.
4. אם $1<\gcd(a,n)<n$ עבור איזשהו a ≤ r, המספר פריק.
5. בצע מ- a = 1 עד ל-הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \scriptstyle \lfloor \scriptstyle {{\sqrt {\varphi (r)}}\log(n)}\scriptstyle \rfloor } (כאן $\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)}}$), המספר פריק.
6. המספר ראשוני.

קישורים חיצוניים

• AKS Primality Test באתר וולפרם אלפא MathWorld (באנגלית)