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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

רקע מתמטי[עריכת קוד מקור | עריכה]

אלגוריתם AKS מבוסס על המשפט המתמטי הבא: מספר טבעי n, גדול מ-2, הוא ראשוני, אם ורק אם מתקיימת הקונגרואנציה הבאה: עבור כל המספרים הזרים ל-n (לא מחויב לכל פרמטר a). המשפט הוא הכללה לפולינומים של המשפט הקטן של פרמה, וניתן להוכיח אותו בעזרת הבינום של ניוטון עם התכונה של מקדם בינומי: לכל k הקטן מ-n, אם ורק אם n הוא ראשוני.

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

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

  1. קלט: מספר טבעי n > 1.
  2. אם n = ab למספרים שלמים a,b > 1, המספר פריק.
  3. מצא r הקטן ביותר כך ש- כאשר הוא הסדר הכפלי של n מודולו r, כלומר: זהו המספר הטבעי הקטן ביותר k כך ש-.
  4. אם עבור איזשהו a ≤ r, המספר פריק.
  5. בצע מ- a = 1 עד ל- (כאן היא פונקציית אוילר)
    1. אם לא קיימים פולינומים f ו-g כך ש- עבור a (כלומר: ), המספר פריק.
  6. המספר ראשוני.

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

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

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