Azgad.com » נס חנוכה, בין “מעוז צור” ל”לטקעס”: התוכנית מצאה תוך שתי דקות שהמספר שתיים בחזקת 400 פחות 593 הוא מספר ראשוני
Azgad.com

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

יבשם עזגד | כתיבת תגובה »   Share on Facebook

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

.
זה מתחיל בקטן
.
זה מתחיל בקטן. למשל, המספרים 2, 3, 5, 7, 11,
ו-13 הם מספרים ראשוניים. אבל כבר בהתחלה מעלה
הרשימה הזאת שאלות גדולות. שאלה ראשונה: האם
יש סוף לרשימה? האם מעבר לגודל מסוים של
מספרים, לא יימצאו עוד "אטומים מתמטיים" שאינם
מתחלקים בשום מספר קטן מהם (מלבד 1)? שאלה
שנייה: האם קיימת חוקיות כלשהי השולטת במרווחים
המשתנים שבין המספרים הראשונים? חוקיות כזו
יכולה לאפשר חיזוי וזיהו של מספרים ראשוניים של
הטבלה המספרית, כמעט ללא מאמץ. היא הייתה
יכולה לרמוז על קיומו של סדר מתמטי יקומי עליון
המונח, אולי, בבסיס כל התופעות הטבעיות. חבל

שעד כה לא נמצא רמז קל שבקלים לקיומה של
חוקיות כזאת. כללית ניתן לראות שככל שמטפסים
במעלה הטבלה – המרחקים בין המספרים
הראשוניים גדלים. ועם זאת, יש גם תופעות הפוכות
(אם כי מקומיות). למשל, מדי פעם מתקיימת תופעה
של מספרים ראשוניים שביניהם מפריד רק מספר אחד.
כזה הם המספרים הראשוניים 3 ו-5; זוג אחר הם
המספרים 5 ו-7. הזוג הבא מורכב מהמספרים
הראשוניים 11 ו-13. הבא אחריהם הוא 29 ו-31.
זוגות נוספים כאלה מפעם לפעם, והחוקיות של
הופעתם אינה ברורה (ולמעשה, לא ברור אם יש בכלל
חוקיות כזאת). גם הסופיות חוזרת ועולה כאן: האם
קיימים אין-סוף זוגות או שמספר הזוגות הוא סופי?

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

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

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

.
מרסן, שהשקיע את ימיו ולילותיו בחקר המספרים
הראשוניים, האמין שעלה בידו למצוא נוסחה
למציאת מספרים ראשוניים. הנוסחה אומרת שהמספר
שתיים (שהוא מספר ראשוני) בחזקת מספר ראשוני
כלשהו, פחות אחת, תמיד ייתן מספר ראשוני. למשל:
שתיים בחזקת שלוש (מספר ראשוני) פחות אחת = 7
(מספר ראשוני), או: שתיים בחזקת חמש (מספר
ראשוני) פחות אחת = 31 (מספר ראשוני).

.
המספרים המתקבלים מנוסחת מרסן קרויים מספרי
מרסן. אבל לפעמים מצביעה הנוסחה הזאת גם על
מספרים לא ראשוניים. למשל: שתיים בחזקת 11
(מספר ראשוני) פחות אחת = 2,047. זהו מספר לא
ראשוני: הוא מתחלק גם ל–23 וגם ל–89. בעיה.
כלומר בניגוד לאמונתו של מרסן, לא כל מספר
שמתגלה באמצעות שיטתו הוא אכן מספר ראשוני.

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

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

.
אתגר מפיו של גאוס
.
רבין הצעיר שמע על גילוי מספר מרסן הראשוני
הגדול ביותר שהיה ידוע אז, ורותק לקסמם של
המספרים הראשוניים. אבל כבר אז היה ברור לו
שמשך הזמן בין גילוי המספרים האלה גדל והולך –
גם בגלל המרווחים הגדלים בין המספרים עצמם וגם
בגלל המוגבלות היחסית של המחשבים. רבין אוהב
לצטט בעניין הזה את קארל פרידריך (1855-1777),
הנחשב בעיני רבים למתמטיקאי הגדול בכל הזמנים
ולמייסדה של המתמטיקה המודרנית. האגדה מספרת
שיום אחד, כאשר גאוס למד בכיתות הנמוכות של
בית-הספר היסודי, התעייף המורה למתמטיקה וחפץ
לנוח. כדי להעסיק את תלמידיו הטיל עליהם משימה:
לסכם את כל המספרים מאחת ועד 1,000. במקום
להתחיל לסכם את כל המספרים, המציא גאוס – בו
במקום – את הנוסחה המתמטית הידועה לחיבור
איבריה של סדרת מספרים טבעיים שלמים. אבל
גאונותו של גאוס לא עמדה לו בחיפושיו אחרי שיטה
יעלה למציאת מספרים ראשוניים. בספרו "מחקרים
בתורת המספרים" הוא כתב ששאלת זיהוים של
מספרים ראשוניים היא אחת השאלות החשובות
והמעניינות בתורת המספרים. "אבל עלינו להודות
שכל השיטות שהוצעו עד כה, או שהן מצומצמות
למקרים מיוחדים (דוגמת מספרי מרסן י"ע) אן שהן
כה קשות לחישוב, עד שלגבי מספרים גדולים ממש
אין הן ניתנות ליישום כלל".

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

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

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

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

.
הרעיון הזה עלה במותו של רבין כששהה בביקור
במכון הטכנולוגי של מסצ'וסטס, ארה"ב (MIT).
אחד מחוקרי מדעי המחשב במכון באותה עת, ווהן
פראט, כתב תוכנית מחשב שהריצה את שיטתו של
רבין, והשניים התחילו "להתעלל" במחשב הקטן
יחסית שהועמד לרשותם. למרות המגבלות הטכניות,
החליטו רבין ופראט לקפוץ כמה שלבים, ולמצוא
כבר בהתחלה מספר ראשוני (שאינו מספר מרסן)
שיעלה בגודלו על המספר הראשוני הכללי הגדול
ביותר שהיה ידוע באותה עת. הם התחילו במספר
שתיים בחזקת 400 פחות אחת, והחלו לרדת ממנו
בהדרגה.
.
נס חנוכה
.
רבין: "ערב אחד, זה היה בחג החנוכה בשנת 1975,
השתתפנו במסיבה יחד עם הרבה ישראלים ששהו
באותו זמן בעיר. ואז התקשר אלי פראט ובאמצע, בין
"מעוז צור" ללטקעס, אמר לי שעכשיו סיים לבדוק
באמצעות התוכנית את שלוש מאות מספרי מרסן
הראשונים בטבלה, והתוכנית הצביעה על כולם;
כלומר, היא אמינה לחלוטין. ואז הוא אמר לי, קח
עיפרון ונייר ותרשום לפניך: התוכנית מצאה תוך שתי
דקות שהמספר שתיים בחזקת ארבע מאות פחות 593
הוא מספר ראשוני. מספר ראשוני כללי גדול יותר לא
היה ידוע אז. עשינו זאת. באותו רגע סמרו לי השערות
מהתרגשות. לא הרבה פעמים מזדמן למתמטיקאי
לפתח שיטה תיאורטית שמשתלבת ופועלת נכון
בניסוי מציאותי. זה היה אחד הרגעים הגדולים בחיי.
הסתכלתי סביבי: החבר'ה שרו, צחקו ואכלו לביבות,
שקלתי לרגע אם לומר להם משהו, אבל בסופו של
דבר חזרתי והצטרפתי למעגל כאילו כלום לא קרה".

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

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

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

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




כתיבת תגובה משלך לקטע