הצגת המקור של הדף "מבחן AKS לראשוניות"

'''מבחן AKS לראשוניות''' הוא [[אלגוריתם]] [[אלגוריתם דטרמיניסטי|דטרמיניסטי]] להוכחת [[מספר ראשוני|ראשוניות]] שנוצר ופורסם על ידי [[מנינדרה אגרוול]], [[ניראג' קיאל]], ו[[ניטין סקסנה]] מ[[המכון ההודי לטכנולוגיה קנפור]],  ונקרא על שמם. האלגוריתם התפרסם ב-[[6 באוגוסט]] [[2002]], במאמרם "PRIMES is in P".{{הערה|[http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PRIMES is in P], המאמר בו התפרסם האלגוריתם.}} החוקרים קיבלו שבחים רבים על עבודתם, כולל [[פרס גדל]] לשנת [[2006]] ו[[פרס פולקרסון]] לשנת [[2006]]. האלגוריתם קובע האם מספר הוא [[מספר ראשוני|ראשוני]] או [[מספר פריק|פריק]] ב[[סיבוכיות זמן|זמן ריצה]] [[פונקציה פולילוגריתמית|פולילוגריתמי]].

זמן הריצה של האלגוריתם המקורי הוא <math>\Omicron(\log^{12}(n))</math> כאשר בהמשך הצליחו לשפרו ל<math>\Omicron(\log^{6}(n))</math>.{{הערה|כיוון=שמאל|{{צ-מאמר|מחבר=H. W. Lenstra Jr. and Carl Pomerance|שם=Primality testing with Gaussian periods|כתב עת=preliminary}}}}

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

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

==קישורים חיצוניים==
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:מבחני ראשוניות]]