החיפוש אחר מספרי מרסן ראשוניים

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

מטרת הפרויקט היא למצוא מספרים ראשוניים מסוג מיוחד, הקרויים מספרי [tTip=על שם הנזיר/משכיל מרן מרסן.]מרסן[/tTip].

חלק 1 מתוך 2: הקדמה על מספרי מרסן

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

הערה: במקום או בנוסף ללקרוא את החלק הזה אתם מוזמנים לצפות בסרטון קצר מ-TED.

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

למשל ארבעת מספרי המרסן הראשונים הם 1,3,7,15; שימו לב שבדיוק שניים מהם ראשוניים.

מי שמכיר טיפ-טיפה מחשבים/אלקטרוניקה בטח זיהה את ארבעת המספרים הנ"ל:

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

למשל M_3 הוא המספר 7 בבסיס 10, והייצוג שלו בבינארי הוא 111 (שלושה אחדים).

(כמובן שניתן גם להסתכל על M_n גם כ-"הכפל את 2 בעצמו n פעמים, ולבסוף החסר 1".)

מספרי מרסן ראשוניים:

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

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

נכון לכתיבת שורות אלה, המספר הראשוני הגדול ביותר שידוע הוא , שהתגלה ב-2013.

זהו מספר בן 17,425,170 ספרות. ניתן לכתוב אותו כ-M_57885161 בכמה תווים, אבל כדי לכתוב אותו כמו שהוא, נידרש למלא אלפי עמודים בספרותיו.

לשם השוואה, מספר האטומים ביקום שלנו מוערך בכ-2 בחזקת 266. זה אומר שאם למשל נניח שקיימים [tTip=1 ואחריו מאה אפסים]גוגול[/tTip] יקומים מקבילים עם אותו מספר אטומים, אז מספר האטומים בכולם ביחד לא מתחיל לגרד את M_57885161.

חלק 2 מתוך 2: מספרי מרסן ומחשבים

איך לעזאזל מוכיחים שמספר כזה הוא ראשוני?

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

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

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

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

האלגוריתם הזה עומד בליבו של הפרויקט [tTip=Great Internet Mersenne Prime Search]GIMPS[/tTip], פרויקט חישוב מבוזר קהילתי שמטרתו למצוא מספרי מרסן ראשוניים. זהו גם אחד מפרויקטי החישוב המבוזר הקהילתי [tTip=1996]הותיקים ביותר[/tTip] ברשת.

דף הבית של הפרויקט: http://www.mersenne.org/

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

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

(המספר המפלצתי M_57885161 שדיברתי עליו בחלק 1 נמצא ע"י מעבד Intel Core2 Duo E8400 בלתי-מזיק.)

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

למה לי להצטרף לחיפוש?

זה אולי יישמע מוזר, אבל אין לי תשובה טובה לשאלה הזאת.

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

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

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

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

למי שבכל זאת מתעניין:

מי שימצא מספר ראשוני יקבל 3000 דולר. אלא אם הוא בחר מספר עם מעל מאה מיליון ספרות, ואז הוא יקבל 50,000 דולרים.

אילו סוגי עבודות קיימים?

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

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

ניתן גם להריץ Trial Factoring - זהו פשוט נסיון לחלק את המספר ב[tTip=לרוב עד 2 בחזקת 80]כל מיני מספרים קטנים יחסית[/tTip]. באופן זה ניתן רק לפסול ראשוניות (אם מצאתם מספר שמחלק), אך לא להוכיח ראשוניות. עבודה זו מומלצת למחשבים חלשים יותר והיא יכולה לקחת גם כמה דקות או שעות.

בנוסף ניתן להריץ P-1 ו-ECM, שאלה עוד שני אלגוריתמים קצת יותר מתוחכמים למציאת גורמים ראשוניים (כלומר גם שני אלה רק פוסלים ראשוניות ולא מוכיחים אותה).

בתור התחלה הייתי ממליץ להריץ LLT (השם המלא הוא Lucas-Lehmer Test) על מחשבים בינוניים ומעלה (שוב, רק אם יש לכם הרבה סבלנות), ו-TF על מחשבים חלשים.

האם הפרויקט יצליח?

הוא כבר הצליח!

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

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

איך משתתפים?

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

לחלק מהפורום התוכנה Prime95 (התוכנה שמשמשת את הפרויקט) תהיה מוכרת:

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

Prime95 היא מהתוכנות המוערכות בתחום לביצוע בדיקה זו (באופציות של התוכנה היא נקראת Torture Test).

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

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

הערה: סתם הזכרתי את זה למי שמתעניין ב-OC. אין שום סיבה לעשות OC בשביל הפרויקט.

ניצול מעבד ואינטרנט של Prime95

כמו בפרויקטים דומים, התוכנה מנצלת רק מחזורים מובטלים (idle cycles) של המעבד.

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

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

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

קיוויתי שההודעה תצא פחות ארוכה אבל לצערי זה לא הצליח.

בכל מקרה אם הותרתי שאלות לגבי הפרויקט רק תגידו.

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