מספר ראשוני – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 84:
=== הוכחת ראשוניות ===
 
כדי להוכיח שמספר נתון '''אינו''' ראשוני, די להציג פירוק שלו לשני גורמים. מכאן שזיהוי מספרים לא ראשוניים הוא בעיה שהיא לפחות ב[[NP (סיבוכיות)|מחלקת הסיבוכיות NP]]. גם בדיקה האם מספר הוא ראשוני שייכת ל-NP, בהתבסס על כך שמספר p הוא ראשוני [[אם ורק אם]] קיים מספר מסדר p-1 ב[[חבורת אוילר]] של p, ותנאי זה ניתן לבדיקה באופן יעיל בהינתן הפירוק של p-1 (כך שהוכחת NP לראשוניות p תכלול את הפירוק הזה ואת המספר מסדר p-1). בשנת 2002 הוכיחוהציגו שלושת[[מנינדרה החוקריםאגרוול]], Agrawal[[נירג' קייל]] ו[[ניטין סקסנה]] אלגוריתם פולינומיאלי להוכחת ראשוניות, הנקרא על שמם [[מבחן AKS לראשוניות]]. Kayalבכך Saxenaהראו שהוכחת ראשוניות שייכת למחלקת הסיבוכיות [[P (סיבוכיות)|P]]{{כ}}{{הערה|1=ראו [http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf#search=%22primes%20is%20in%20p%22 מאמרם של אגרוול ועמיתיו]}}. לפיכך,ולפיכך שייכת ל-P גם הבעיה הדואלית היא ב-P (האם מספר אינו ראשוני).
 
=== מבחני ראשוניות ===