מספר ראשוני

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

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

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

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

המספר 12 אינו ראשוני שכן ניתן להציגו כמכפלה של המספרים 3 ו-4. המספר 11 הוא ראשוני, שכן אינו ניתן להצגה כמכפלה של שני מספרים טבעיים קטנים ממנו.

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

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

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

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

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

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

ברור שלכל מספר גדול מ-1 יש גורם ראשוני (זו טענה שאפשר להוכיח באינדוקציה מתמטית). נניח שיש רק מספר סופי של ראשוניים, \ p_1,\dots,p_n. המספר \ N = p_1\dots p_n+1 (מכפלת n הראשוניים הללו פלוס 1) אינו מתחלק באף אחד מהם, ולכן אין לו גורמים ראשוניים - אבל זו סתירה לכך ש- \ N>1. מכאן שאין רשימה סופית הכוללת את כל הראשוניים.

כאשר סופרים את הראשוניים בקטעים ארוכים (כגון: עד 1000, בין 1000 ל-2000, וכן הלאה), מגלים ששכיחותם הולכת ויורדת. גאוס עסק רבות בחישובים בקשר לסוגיה זו, ושיער ששכיחות הראשוניים בין 1 ל-x יורדת, בקירוב, ביחס הפוך ללוגריתם הטבעי של x. כחמישים שנים אחר-כך חקר רימן את פונקציית זטא הקרויה על שמו, במטרה להוכיח את ההשערה של גאוס. על היסודות שהניח רימן, הצליחו לבסוף המתמטיקאים של סוף המאה ה-19 להוכיח את משפט המספרים הראשוניים: מספר הראשוניים הקטנים ממספר נתון x שווה בקירוב ל- :\ \frac{x}{\ln(x)} כאשר \ \ln(x) הוא הלוגריתם הטבעי של \ x.

ממשפט המספרים הראשוניים אפשר להסיק היכן נמצא, בקירוב, הראשוני ה-n-י, \ p_n: \ p_n \sim n\,\mbox{ln}\,n. ליתר דיוק, עבור כל שלם \ n\ge 6, מתקיים \ n\,\mbox{ln}\,n<p_n<n(\mbox{ln}\,n+\mbox{ln}\,\mbox{ln}\,n).

לפי השערת ברטראן (שהוכחה במאה התשע-עשרה), יש מספר ראשוני בכל קטע מהצורה \ [n,2n]. עם זאת, לא ידוע האם לכל n טבעי קיימים ראשוניים בקטע \ [n^2,(n+1)^2].

ברווח שבין ראשוניים סמוכים עוסקת השערת הראשוניים התאומים.

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

לא קיים פולינום שאינו קבוע, אפילו בכמה משתנים, המקבל (כאשר מציבים בו מספרים שלמים) רק ערכים ראשוניים. לתוצאה זו יש הכללות רבות. למשל, היא נכונה גם עבור פונקציות אלגבריות (פונקציה F היא אלגברית אם קיים פולינום P כך ש- \ P(F(z))=0; לדוגמה, \ F(z) = \sqrt[3]{z^2+\sqrt{z}} אלגברית). פונקציה מהצורה \ \sum_{i=1}^{m} P_i(x_1,\dots,x_n) a_i^{Q(x_1,\dots,x_n)}, שבה הפולינומים \ P_i,Q_i בעלי מקדמים שלמים, והמספרים \ a_i שלמים, שאינה קבועה, אינה יכולה לקבל רק ערכים ראשוניים כאשר מציבים במשתנים \ x_1,\dots,x_n ערכים טבעיים‏[1].

לעומת זאת, אפשר להציג מספרים ראשוניים באמצעות פונקציות שאינן אלגבריות. לדוגמה, אם מגדירים את הפונקציה \ d(x,y) = \max(x-y,0), ו- \ r(y,x) היא השארית של y בחלוקה ל- x (עם \ r(y,0)=y), אז הראשוני ה-n-י מתקבל מהנוסחה \ p_n = \sum_{i=0}^{n^2} d(1,d(\sum_{j=0}^{i}r(d(j,1)!^2,j),n))[2]. בעזרת טכניקות שפותחו במסגרת פתרון הבעיה העשירית של הילברט, נמצאו פולינומים \ P(x_1,\dots,x_n) בעלי מקדמים שלמים, כך שקבוצת הערכים הטבעיים שהפולינום מקבל, כאשר מציבים ב- \ x_1,\dots,x_n מספרים טבעיים, מתלכדת עם קבוצת המספרים הראשוניים‏[3].

משפט מילס קובע כי קיים קבוע A כך ש-[A^{3^n}] ראשוני לכל n טבעי (כאשר [\cdot] היא פונקציית הערך השלם).

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

את משפט המספרים הראשוניים הכליל דיריכלה לסדרות חשבוניות: אם \ a,n הם מספרים זרים, אז ישנם אינסוף מספרים ראשוניים השקולים ל-\ a מודולו \ n. דיריכלה הוכיח שבכל \ n, המספרים הראשוניים מפוזרים באופן אחיד בקירוב, בין \ \phi(n) השאריות האפשריות מודולו \ n. אם \ \pi(x,n,a) מייצג את כל המספרים הראשוניים בטווח \ [2,x] השקולים ל-\ a מודולו \ n, כאשר \ \mbox{gcd}(a,n)=1, אזי

\ \pi(x,n,a) \sim \frac{x}{\phi(n)\,\mbox{ln}\,x}.

לעומת זאת, לא ידוע האם יש אינסוף ראשוניים מצורות שאינן לינאריות, כגון \ n^2+1.

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

ידוע שסכום הטור ההרמוני \ \sum_{n\leq x} \frac{1}{n} הוא \ \ln(x)+\gamma+o(1) (כאשר \ \gamma הוא הקבוע של אוילר). לעומת זאת, כאשר מסכמים על ראשוניים בלבד, \ \sum_{p \leq x}\frac{1}{p} = \ln\ln(x)+B+o(1), כאשר B קבוע. ובפרט טור ההופכיים של המספרים הראשוניים מתבדר.

באופן דומה, המכפלה \ \prod_{n=2}^{N} (1-1/n) = \frac{1}{N}, בעוד ש- \ \prod_{p\leq N}(1-1/p) \sim \frac{e^{-\gamma}}{\ln(N)}.

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

המספרים הראשוניים הקטנים ביותר הם 2, 3, 5, 7, 11, 13 ו-17.

המספר הגדול ביותר שידוע שהוא ראשוני הוא \ 2^{57,885,161}-1 (התגלה ב-25 בינואר 2013; כאחדים מקודמיו, מספר זה התגלה באמצעות חישוב מבוזר קהילתי): למספר זה 17,425,170 ספרות עשרוניות. זהו גם מספר מרסן הראשוני ה-48‏[4]. קדם לו המספר \ 2^{43,112,609}-1 שהוא מספר מרסן הראשוני ה-47, והראשון שהתגלה עם יותר מעשרה מיליון ספרות ובכך הוא עומד בתנאים לפרס בן $100,000 מטעם קרן החזית האלקטרונית[5].

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

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

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

מציאת כל המספרים הראשוניים בין 2 ל-120 באמצעות הנפה של ארטוסתנס.

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

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

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

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

כדי להוכיח שמספר נתון אינו ראשוני, די להציג פירוק שלו לשני גורמים. מכאן שזיהוי מספרים לא ראשוניים הוא בעיה שהיא לפחות במחלקת הסיבוכיות NP. גם בדיקה האם מספר הוא ראשוני שייכת ל-NP, בהתבסס על כך שמספר p הוא ראשוני אם ורק אם קיים מספר מסדר p-1 בחבורת אוילר של p, ותנאי זה ניתן לבדיקה באופן יעיל בהינתן הפירוק של p-1 (כך שהוכחת NP לראשוניות p תכלול את הפירוק הזה ואת המספר מסדר p-1). בשנת 2002 הוכיחו שלושת החוקרים Agrawal Kayal Saxena שהוכחת ראשוניות שייכת למחלקת הסיבוכיות P‏‏[6]. לפיכך, גם הבעיה הדואלית היא ב-P (האם מספר אינו ראשוני).

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

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

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

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

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

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

שפי גולדווסר וג'ו קיליאן הציעו אלגוריתם אקראי למבחן ראשוניות המתבסס על עקום אליפטי, שזמן הריצה שלו פולינומי כמעט עבור כל קלט. בהתבסס על רעיון זה, פיתח ארתור אטקין אלגוריתם דטרמיניסטי יעיל מאוד מבחינה מעשית לבדיקת ראשוניות הנקרא Atkin's test. יתרונה של הגישה הוא שהיא מספקת הוכחות קצרות לראשוניות (primality certificate).

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

מבחינה תאורטית לפחות סוגיית הסיבוכיות של בדיקת ראשוניות יושבה ב-2002 כששלושה מדעני מחשב הודיים, אגרוול, קייל וסקסנה, הראו אלגוריתם פולינומי דטרמיניסטי לבדיקת ראשוניות הנקרא על שמם AKS. האלגוריתם מבוסס על הכללה של המשפט הקטן של פרמה לחוגי פולינומים מעל שדות סופיים. סיבוכיות האלגוריתם היא בסביבות \ O(\mbox{log}^6(n))[7].

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

חוג המספרים השלמים אינו אלא אחד מני תחומי שלמות רבים. בתחום שלמות כללי יש שני סוגי איברים שאפשר לראות בהם הכללה של המספרים הראשוניים: איבר אי-פריק של תחום שלמות הוא איבר a (לא הפיך ושונה מאפס) שאין לו מחלקים לא טריוויאליים, כלומר, אם a=bc אז כל אחד משני הגורמים b ו-c הוא הפיך או כפולה של a באיבר הפיך. איבר p הוא איבר ראשוני, אם כל אימת ש-p מחלק מכפלה bc, הוא מחלק את אחד הגורמים שלה. כל איבר ראשוני הוא אי-פריק, אבל ההיפך אינו בהכרח נכון. בחוג השלמים שני המושגים מתלכדים (זוהי הלמה של אוקלידס), ומגדירים את המספרים הראשוניים המוכרים, והמספרים הנגדיים להם: \ 2, -2, 3, -3, ....

התכונה הבסיסית של המספרים הראשוניים (בחוג השלמים) מתבטאת במשפט היסודי של האריתמטיקה: כל מספר אפשר לפרק לגורמים ראשוניים, באופן יחיד. גם כאן, כשבוחנים תחום שלמות כללי במקום חוג השלמים, שתי התכונות האלה עשויות שלא להתקיים. ישנם תחומי שלמות שבהם הראשוניים נדירים יותר, וקיים פירוק לגורמים אי-פריקים, אבל לא לגורמים ראשוניים (לדוגמה: בחוג \ \mathbb{Z}[\sqrt{-6}] אפשר לפרק \ 6 = 2 \cdot 3 = -\sqrt{-6} \cdot \sqrt{-6}; הגורמים אי-פריקים אבל אינם ראשוניים). ישנם גם תחומי שלמות שבהם אין פירוק אפילו לגורמים אי-פריקים (אלו חוגים שאינם נתריים). עם זאת, כאשר קיים פירוק לגורמים ראשוניים, הוא יחיד (אפילו בין כל הפירוקים לגורמים אי-פריקים). בתחומים ראשיים, כל איבר אי-פריק הוא ראשוני, ויש פירוק יחיד לגורמים.

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

  • השערת גולדבך - האם כל מספר זוגי גדול מ-2 ניתן לרשום כסכום של שני ראשוניים?
  • השערת המספרים הראשוניים התאומים - האם יש אינסוף זוגות של מספרים ראשוניים שההפרש ביניהם הוא 2?
  • האם לכל d טבעי קיימים אינסוף זוגות של מספרים ראשוניים שההפרש ביניהם הוא 2d? (הכללה של שתי ההשערות הקודמות).
  • האם יש אינסוף מספרי פיבונאצ'י ראשוניים?
  • האם יש אינסוף מספרי פרמה ומספרי מרסן ראשוניים?
  • האם יש אינסוף מספרים ראשוניים מהצורה \ n^2+1? (בתורת המספרים השאלה ידועה כבעיית אוילר); Iwaniac הוכיח (1972), בעזרת שיטת הנפה, שיש אינסוף מספרים מהצורה האמורה שיש להם לכל היותר שני גורמים ראשוניים.

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

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

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

  1. ^ Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 4.4
  2. ^ James Jones, Formula for the n'th prime number, Canad. Math. Bull. 18(3) (1975)
  3. ^ Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 1
  4. ^ Largest Known Prime, 48th Known Mersenne Prime Found!!, באתר GIMPS
  5. ^ EFF Cooperative Computing Awards
  6. ^ ראו מאמרם של אגרוול ועמיתיו
  7. ^ ראו מאמרם של אגרוול ועמיתיו