מספר ראשוני

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

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

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

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

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

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

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

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

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

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

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

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

ממשפט המספרים הראשוניים אפשר להסיק היכן נמצא, בקירוב, הראשוני ה-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)$ .

לא קיים פולינום שאינו קבוע, אפילו בכמה משתנים, המקבל (כאשר מציבים בו מספרים שלמים) רק ערכים ראשוניים. לתוצאה זו יש הכללות רבות. למשל, היא נכונה גם עבור פונקציות אלגבריות (פונקציה 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,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.

ב-4 בספטמבר 2006 התגלה המספר הראשוני הגדול ביותר הידוע כיום: $\ 2^{32,582,657}-1$ . למספר זה 9,808,358 ספרות עשרוניות; כאחדים מקודמיו, מספר זה התגלה באמצעות חישוב מבוזר קהילתי. זהו גם מספר מרסן הראשוני ה-44. לאדם הראשון או הקבוצה הראשונה שימצאו מספר ראשוני בעל עשרה מיליון ספרות לפחות ממתין פרס בן $100,000 מטעם ה- Electronic Frontier Foundation.

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

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

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

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

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

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

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

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

כדי להוכיח שמספר נתון אינו ראשוני, די להציג פירוק שלו לשני גורמים. מכאן שזיהוי מספרים לא ראשוניים הוא בעיה במחלקת הסיבוכיות NP. גם ההיפך נכון: מספר p הוא ראשוני אם ורק אם קיים מספר מסדר p-1 בחבורת אוילר של p ^[4]; זו טענה חישובית שאפשר לבדוק בזמן סופי, ולכן גם זיהוי מספרים ראשוניים הוא בNP. למעשה, קיימת הוכחה לראשוניות הדורשת רק 87 פעולות חיבור וכפל ^[5], אלא שמציאת הוכחה כזו דורשת מאמץ חישובי רב ביותר.

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

הדרך הנאיבית לבדיקת ראשוניות של מספר נתון נקראת "חלוקה נסיונית" (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))$ ^[6].

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

התכונה היסודית של המספרים הראשוניים, היינו, העובדה שכל מספר שלם הוא מכפלה של ראשוניים באופן יחיד, אינה נכונה בחוגי שלמים אחרים. לדוגמה, בחוג המספרים השלמים בשדה $\ \mathbb{Q}[\sqrt{-6}]$ , המתקבל מסיפוח השורש של $\ -6$ למספרים הרציונליים, הפירוק לגורמים קיים, אך אינו יחיד.

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

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

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

[עריכה] ראו גם

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

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

[עריכה] הערות שוליים

^ Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 4.4
^ James Jones, Formula for the n'th prime number, Canad. Math. Bull. 18(3) (1975)
^ Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 1
^ ראו הסבר על מאמרו של וון פרט מ- 1975
^ Diophantine Representation of the set of prime numbers, Jones, Sato, Wada and Wiens, JAMS 1976, Thm. 5
^ ראו מאמרם של אגרוול ועמיתיו

See also ebooksgratis.com: no banners, no cookies, totally FREE.