מספר ראשוני

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

מספר ראשוני הוא מספר טבעי גדול מאחד המתחלק ללא שארית בשני מספרים בלבד: בעצמו ובאחד, להבדיל ממספר פריק.

המספרים הראשוניים הראשונים הם -

2, 3, 5, 7, 11, 13, 17 ...

המספר 1 אינו נחשב ראשוני. אחת הסיבות לכך היא שהוספתו לראשוניים הייתה פוגמת בניסוח המשפט היסודי של האריתמטיקה (ראו להלן).

תוכן עניינים

1 משפטים
2 אלגוריתמים
- 2.1 מציאת כל המספרים הראשוניים הקטנים ממספר נתון
- 2.2 בדיקת ראשוניות
3 קוד RSA
4 הכללה
5 שאלות פתוחות
6 ראו גם
7 לקריאה נוספת

[עריכה] משפטים

[עריכה] המשפט היסודי של האריתמטיקה

"המשפט היסודי של האריתמטיקה" קובע שלכל מספר טבעי קיימת הצגה יחידה כמכפלת מספרים ראשוניים (למשל: $\ 7\times 2\times 2 = 28$ ). תכונה זו של המספרים הראשוניים הופכת אותם למעין "אטומים" המרכיבים את המספרים השלמים.

תהליך מציאת המספרים הראשוניים שמכפלתם נותנת מספר נתון נקרא פירוק לגורמים.

[עריכה] קיום אינסוף מספרים ראשוניים

ניתן להוכיח בדרכים אחדות שקיים מספר אינסופי של מספרים ראשוניים. הוכחה ראשונה לכך מופיעה בספרו של אוקלידס, "יסודות":

נניח שיש רק מספר סופי של ראשוניים. ניקח את כל הראשוניים הללו, נכפיל אותם זה בזה ונוסיף 1. התוצאה שקיבלנו נותנת שארית 1 בחלוקה לכל אחד מהמספרים הראשוניים. לכן תוצאה זו אינה מתחלקת באף אחד מהראשוניים – היא חייבת להיות מספר ראשוני נוסף, או להתחלק במספר ראשוני שאינו ברשימת המספרים הראשוניים שלנו. בכל מקרה קיבלנו שההנחה שיש מספר סופי של ראשוניים מובילה לסתירה, ולכן הנחה זו אינה נכונה, כלומר יש מספר אינסופי של ראשוניים.

[עריכה] משפט המספרים הראשוניים

כמה מספרים ראשוניים קטנים ממספר נתון? התשובה לשאלה זו ניתנת במשפט המספרים הראשוניים, שקובע כי מספר הראשוניים הקטנים ממספר נתון $x$ שווה בקירוב ל-

$\frac{x}{\ln(x)}$

כאשר $\ \ln(x)$ הוא הלוגריתם הטבעי של $x$ .

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

[עריכה] מציאת כל המספרים הראשוניים הקטנים ממספר נתון

הנפה של ארטוסתנס היא אלגוריתם פשוט למציאת כל המספרים הראשוניים הקטנים ממספר נתון:

רשום את כל המספרים הטבעיים מ־2 ועד למספר הנתון.
סמן כראשוני את המספר הראשון ברשימה שטרם סומן.
עבור על כל שאר הרשימה ומחק כל מספר שמתחלק ללא שארית במספר שסומן בשלב הקודם.
אם עדיין לא הגעת לסוף הרשימה, חזור לשלב השני.

בצעד ראשון באלגוריתם נסמן את 2 כראשוני, ונמחק את כל שאר המספרים שמתחלקים ב־2. בצעד שני נסמן את 3 כראשוני, ונמחק את כל שאר המספרים שמתחלקים ב־3. בצעד שלישי באלגוריתם נסמן את 5 כראשוני (את 4 מחקנו בצעד הראשון), ונמחק את כל שאר המספרים שמתחלקים ב־5, וכך הלאה עד לסיום האלגוריתם.

"הנפה של ארתוסתנס" יעילה (מבחינת סיבוכיות הזמן הנדרש לביצוע המשימה) ליצירת רשימה לא גדולה, של מספרים ראשוניים הקטנים מגבול מסוים. אך אינה יעילה לבדיקת ראשוניות של מספר נתון. קיימים מספר דרכים לבדיקת ראשוניות של מספר.

[עריכה] בדיקת ראשוניות

הוכח שבעיית הוכחת ראשוניות כלומר מציאת גורם לא טריוויאלי של $\ n$ , הנה במחלקת הסיבוכיות NP. כלומר אם $\ n$ אינו ראשוני ניתן להוכיח זאת בקלות.

הדרך הנאיבית ביותר לבדיקת ראשוניות נקראת "חלוקה נסיונית" (Trial division) והיא ניסיון לחלק את המספר הנתון בכל המספרים (או הראשוניים) מ־2 ועד לשורש הריבועי של המספר הנתון. חלוקה נסיונית מבוססת על הנפה של ארתוסטנס והייתה ידועה עוד מימיה של יוון העתיקה. אולם שיטה זו אינה יעילה כאשר מדובר בבדיקת מספר גדול (בן מאות ספרות עשרוניות) וסיבוכיותה היא $\ O(\sqrt{n})$ .

אפשר לבצע בדיקת ראשוניות יעילה הרבה יותר באמצעות משפט פרמה הקטן עבור כל ראשוני $\ p$ ושלם $\ a$ כלשהו, השוויון $a^{p-1} \equiv 1 (\mbox{ mod }p)$ מתקיים. קיימים אלגוריתמים יעילים לחישוב הערך $\ a^{n-1}$ (מודולו $\ n$ ), עבור השלמים $\ a$ ו- $\ n$ כלשהם. כגון אלגוריתם ריבוע וכפל (העלאה בריבוע באופן חוזר ונשנה) שסיבוכיותו פולינומיאלית, מה שמאפשר בדיקת ראשוניות יעילה. אולם מבחן זה אינו מדויק מאחר וישנם מספרים פריקים מסוימים המקיימים את משפט פרמה הקטן.

גרי מילר ניצל תכונות ידועות של משפט פרמה הקטן ליצירת אלגוריתם דטרמיניסטי פולינומיאלי למבחן ראשוניות המתבסס על השערת רימן המורחבת (ERH). פרופסור מיכאל רבין (האוניברסיטה העברית) הרחיב את האלגוריתם מייד לאחר מכן, למבחן ראשוניות פולינומיאלי ראנדומלי. סולוביי ושטראסן המציאו אלגוריתם למבחן ראשוניות ראנדומלי המבוסס על סימבול יעקובי. עבור $\ n$ ראשוני כלשהו $\ \left(\frac{a}{n} \right) = a^{{n-1 \over 2}} (\mbox{mod }n)$ מתקיים עבור כל $\ a$ . גם אלגוריתם זה ניתן להרחבה למבחן ראשוניות דטרמיניסטי, תחת השערת רימן המורחבת. גולדווסר וקיליאן הציעו אלגוריתם ראנדומלי למבחן ראשוניות המתבסס על עקומה אליפטית, שזמן ריצתו פולינומיאלי כמעט עבור כל קלט.

בהתבסס על רעיון זה, פיתח אטקין אלגוריתם דטרמיניסטי יעיל מאוד מבחינה מעשית לבדיקת ראשוניות הנקרא Atkin's test. ב-2002 פרסם צוות מתמטיקאים הודיים אלגוריתם מבחן ראשוניות דטרמיניסטי הנקרא AKS, המבוסס על הכללה של משפט פרמה הקטן לחוגים פולינומיאליים מעל שדות סופיים. ההערכה שהיא שסיבוכיות האלגוריתם היא בסביבות $\ O(\mbox{log}^6(n))$ .

אלגוריתמים לבדיקת ראשוניות מתחלקים לשני סוגים עיקריים:

אלגוריתם בדיקת ראשוניות אקראי, כמו אלגוריתם מילר רבין ואחרים. האלגוריתם מקבל מספר כלשהו ומחזיר תשובה "אמת" או "שקר" לגבי ראשוניותו. אלגוריתם זה אינו מחזיר תשובה מוחלטת לגבי ראשוניות המספר הנבדק, אלא רק בהסתברות גבוהה. במונח הסתברות גבוהה מתכוונים כי גם אם האלגוריתם החזיר "אמת" לגבי מועמד נתון, יש סיכוי נמוך (בהתאם לפרמטרים של האלגוריתם) כי המספר אינו ראשוני. אולם במידה והאלגוריתם מחזיר "שקר" לגבי ראשוניות המספר, משמעות הדבר כי המספר פריק בוודאות. האלגוריתם עושה שימוש במספרים אקראיים, כדי לבצע החלטות, משום כך מכונה אלגוריתם אקראי.
בדיקת ראשוניות דטרמיניסטית, נקראת גם בדיקת ראשוניות אמיתית. בניגוד לשיטה הקודמת. אלגוריתמים מסוג זה מחזירים תשובה וודאית לגבי ראשוניות המספר. חלקם אף מספקים תווית המאפשרת לאמת את תשובת האלגוריתם בקלות. אולם סיבוכיותם של אלגוריתמים אלו גבוהה יותר בדרך כלל.

בדיקת ראשוניות דרושה לעיתים קרובות בהצפנה בעיקר במערכת מפתח-פומבי כגון RSA. מבחינה מעשית בדיקת ראשוניות דטרמיניסטית אינה נחוצה במקרים רבים. שימוש זהיר באלגוריתם אקראי דוגמת מילר רבין, מאפשר הפקת ראשוניים גדולים ביעילות רבה, אשר ראשוניותם מוכחת בהסתברות גבוהה ביותר, עד כי האפשרות כי תיפול טעות זניחה.

[עריכה] קוד RSA

מספרים ראשוניים עומדים בבסיסו של קוד RSA להצפנה במפתח ציבורי. הקוד מתבסס על הקלות (היחסית) שבה ניתן למצוא מספרים ראשוניים גדולים (בני מאות ספרות), ועל הקושי העצום לפרק לגורמים מספר גדול, שהוא מכפלה של שני מספרים ראשוניים.

[עריכה] הכללה

בתחום שלמות, איבר ראשוני הוא איבר לא הפיך p, שאינו מחלק מכפלה ab אלא אם הוא מחלק את אחד הגורמים שלה. לפי הגדרה זו, האיברים הראשוניים בחוג המספרים השלמים הם המספרים הראשוניים המוכרים, והמספרים הנגדיים להם (כלומר: $\ 2, -2, 3, -3, ...$ ).

[עריכה] שאלות פתוחות

השערת גולדבך - האם כל מספר זוגי גדול מ-2 ניתן לרשום כסכום של שני ראשוניים?
השערת הראשוניים התאומים - האם יש אינסוף זוגות של מספרים ראשוניים שההפרש ביניהם הוא 2?
האם לכל n טבעי קיימים אינסוף זוגות של מספרים ראשוניים שההפרש ביניהם הוא 2n? (הכללה של ההשערה הקודמת).
האם כל מספר זוגי אפשר לרשום כהפרש של שני מספרים ראשוניים?
האם יש אינסוף מספרי פיבונצ'י ראשוניים?
האם יש אינסוף מספרי פרמה ומספרי מרסן ראשוניים?
האם לכל n טבעי קיימים ראשוניים בין n² לבין n + 1)²)?
האם יש אינסוף ראשוניים מהצורה n²+1 כאשר n שלם?