עמוד הבית > מתמטיקה וסטטיסטיקה
גליליאו : כתב עת למדע ומחשבה


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



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


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

מספרים טבעיים גדולים מ-1, כאלה שיש להם בדיוק שני מחלקים, משכו תשומת לב כבר במאה החמישית לפנה"ס. המספרים: 2, 3, 5, 7, 11,... 101, 103, 107,... נקראים ראשוניים (Prime Numbers). מספרים טבעיים שאינם ראשוניים נקראים פריקים.

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

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

ידועות הוכחות אחדות לעובדה שקיימים אינספור מספרים ראשוניים. הקצרה והחביבה שבהן, אף היא על דרך השלילה, הולכת כך: אילו היתה רק כמות סופית (k) של מספרים ראשוניים, היינו מסדרים אותם בסדר עולה כך שהאחרון היה הראשוני הגדול מכולם: p1, p2, p3,..., pk. בנסיבות אלה, המספר n שמתקבל מהוספת 1 למכפלתם: p1 p2 p3 ...pk + 1 = n אינו יכול להיות ראשוני (הוא גדול מ-pk, שהוא הראשוני הגדול מכולם) ואינו יכול להיות פריק (חילוקו בכל אחד מהמספרים הראשוניים p1,..., pk, מותיר שארית 1). לפיכך, ההנחה כי יש ראשוני גדול מכולם מובילה לסתירה. מספר הראשוניים, אם כן, אינו יכול להיות סופי.

מיהו ראשוני?

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

לא קשה להשתכנע בוודאות כי הטבעי 313 הוא ראשוני: בודקים שאינו מתחלק ב-2, ב-3, ובכל ראשוני שאינו גדול מ-17 (מיותר לחפש מחלקים גדולים מהשורש הריבועי של 313). כשהשאלה נוגעת ל-3131313 ההכרעה מידית – 3131313 פריק כי סכום ספרותיו, ולכן גם הוא, מתחלק ב-30. בהכרעת ראשוניות הטבעי 313131313 המלאכה מתארכת עד מאוד וכדאי להשתמש במחשב.

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

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

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

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

צפיפות

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

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

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

צפיפות הראשוניים בתוך הטבעיים היא (log(n/י11בקירוב. תוצאה זו ידועה כמשפט המספרים הראשוניים. לג'נדר הגיע לקירוב טוב וגאוס, שקירוביו היו טובים אף הם, הסיק את התוצאה מבלי שהצליח להוכיחה. המשפט נוסח והוכח ב-1896 על ידי הדמר (Hadamard) ו-וולה פוסין (Vallee Poussin) אחרי שכבר פורסמו תוצאות מרשימות (אך לא שלמות) של מתמטיקאים אחרים, בהם צ'ביצ'ב (Chebyshev) ורימן (Riemann).

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

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

משפט מעניין הוא משפט ווילסון (n :(Wilson ראשוני אם ורק אם הוא מחלק את n-1)!+1). משפט זה מעניין כי הוא מציג תנאי הכרחי ומספיק לראשוניות (קצר וגם אלגנטי). לדוגמה: 5 מחלק את 25=י1x2x3x4+1י=1+!4. הוכחת המשפט אינה מורכבת במיוחד, והיא מראה ישירות את הסיבוכיות המבנית בהכרעת ראשוניות.

ביבליוגרפיה:
כותר: בעקבות ראשוניים
מחברת: טל, ג'ודי (ד"ר)
תאריך: נובמבר-דצמבר 2002 , גליון 52
שם כתב העת: גליליאו : כתב עת למדע ומחשבה
הוצאה לאור: SBC לבית מוטו תקשורת ולאתר IFEEL
הערות לפריט זה: 1. ד"ר ג'ודי טל, בעלת מכון לפיתוח צוותים - LearningCycles. התמחתה במתמטיקה ובהיסטוריה ובפילוסופיה שלה. judyt@netvision.net
הספרייה הוירטואלית מטח - המרכז לטכנולוגיה חינוכית