מספר ראשוני – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←הוכחת ראשוניות: ניסוח |
|||
שורה 84:
=== הוכחת ראשוניות ===
כדי להוכיח שמספר נתון '''אינו''' ראשוני, די להציג פירוק שלו לשני גורמים. מכאן שזיהוי מספרים לא ראשוניים הוא בעיה שהיא לפחות ב[[NP (סיבוכיות)|מחלקת הסיבוכיות NP]]. גם בדיקה האם מספר הוא ראשוני שייכת ל-NP, בהתבסס על כך שמספר p הוא ראשוני [[אם ורק אם]] קיים מספר מסדר p-1 ב[[חבורת אוילר]] של p, ותנאי זה ניתן לבדיקה באופן יעיל בהינתן הפירוק של p-1 (כך שהוכחת NP לראשוניות p תכלול את הפירוק הזה ואת המספר מסדר p-1). בשנת 2002
=== מבחני ראשוניות ===
|