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

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

זמן הריצה של האלגוריתם המקורי הוא $O (\log^{12} (n))$ כאשר בהמשך הצליחו לשפרו ל $O (\log^{6} (n))$ .תבנית:הערה

רקע מתמטי

אלגוריתם AKS מבוסס על המשפט המתמטי הבא: בהינתן מספר שלם n, גדול מ-2, ומספר שלם a, זר ל-n, המספר n הוא ראשוני אם ורק אם מתקיימת הקונגרואנציה (הפולינומית) הבאה: $(x - a)^{n} \equiv (x^{n} - a) (\mod n)$ . המשפט הוא הכללה לפולינומים של המשפט הקטן של פרמה, וניתן להוכיח אותו בעזרת הבינום של ניוטון עם התכונה של מקדם בינומי: $(\binom{n}{k}) \equiv 0 (\mod 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 (\mod r)$ .
אם $1 < \gcd (a, n) < n$ עבור איזשהו a ≤ r, המספר פריק.
בצע מ- a = 1 עד ל-⌊φ(r)log⁡(n)⌋ (כאן φ היא פונקציית אוילר)
1. אם לא קיימים פולינומים f ו-g כך ש- $(X + a)^{n} - (X^{n} + a) = n f (x) + (x^{r} - 1) g (x)$ עבור a (כלומר: $(X + a)^{n} \equiv̸ (X^{n} + a) (\mod (n, x^{r} - 1))$ ), המספר פריק.
המספר ראשוני.