מבחן 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 הוא ראשוני.

האלגוריתם[עריכת קוד מקור | עריכה]

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

  1. קלט: מספר טבעי n > 1.
  2. אם n = ab למספרים שלמים a,b > 1, המספר פריק.
  3. מצא r הקטן ביותר כך ש-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 עד ל-\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. המספר ראשוני.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ PRIMES is in P, המאמר בו התפרסם האלגוריתם.