GIMPS
GIMPS (Great Internet Mersenne Prime Search), הוא מיזם חישוב מבוזר קהילתי, המשתמש באינטרנט, לחיפוש אחר מספרי מרסן ראשוניים, ובו משתתפים קרוב ל-241,000 מתנדבים וברשותם כ-2,400,000 מחשבים.
פרויקט GIMPS נוסד על ידי ג'ורג' וולטמן, שכתב את קוד המקור לתוכנות Prime95 ו-MPrime עבור הפרויקט. סקוט קוורסקי כתב את PrimeNet, שרת אינטרנטי שתומך במחקר ומדגים את תוכנת המחשוב המבוזר של חברת "אנטרופיה", חברה שייסד בשנת 1997.
עם התפתחות תורת המספרים פותחו כלים רבים הממקדים ומקלים את החיפוש אחר מספרים ראשוניים. אחד הכלים, שפותח והוכח בידי האב מרן מרסן, נתן תבנית לאפשרות לאתר מספר ראשוני והיא , כאשר P עצמו חייב להיות מספר ראשוני. בהמשך פותח מבחן לוקאס-להמר למספרי מרסן שמקל עוד יותר על החיפוש ובורר את האפשרויות הקיימות במטרה להגדיל את סיכויי הצלחת החיפוש.
היסטוריה
פרויקט GIMPS החל את דרכו בשנת 1996, והציע לגייס את יכולת החישוב של אלפי מחשבים, במטרה למצוא מספרי מרסן ראשוניים גדולים. נכון לשנת 2021 ידועים לאנושות 51 מספרי מרסן, מתוכם, 17 האחרונים נמצאו על ידי פרויקט GIMPS.
נכון לשנת 2021, גודל המספרים שאותם בודק הפרויקט דורש זמן הרצה של חודש עד 3 חודשים על מחשב מודרני, על מנת לחשב ולקבוע האם מספר הוא מספר מרסן ראשוני.
החל מתחילת המאה ה-21 התפתח מאוד התחום של חישוב מבוזר קהילתי. מציאת מספר ראשוני כרוכה בפעולות חישוביות רבות, אך ניתן לחלק את כלל המספרים לבדיקה בין משתמשים רבים כך שכל אחד בודק מספר אחר, ובדרך כלל יוקצה מספר זהה לשני בודקים שונים. בדרך זו גדלים הסיכויים למצוא מספרים אלה, אם כי בהחלט ייתכן שמספר גדול יותר יימצא לפני מספרים קטנים ממנו. למעשה, נכון לנובמבר 2021, נבדקו כל מספרי מרסן ברצף עד המספר לפחות פעם אחת.[1]
הגוף שנטל על עצמו את ניהול המספרים, הקצאתם לבדיקה ובדיקת התוצאות החוזרות הוא GIMPS. גוף זה גם מכריז על מספרי מרסן ראשוניים חדשים שנתגלו, מעת לעת.
- ב-23 באוגוסט 2008 התגלה מספר מרסן הראשוני ה-47, . מספר זה, שהתגלה במחלקה למתמטיקה של אוניברסיטת קליפורניה בלוס אנג'לס, הוא בן 12,978,189 ספרות עשרוניות. מספר זה הוכרז כמנצח הפרס בן $100,000 מטעם קרן החזית האלקטרונית.
- ב-6 בספטמבר 2008 התגלה מספר מרסן הראשוני ה-45, . למספר זה 11,185,272 ספרות עשרוניות והוא התגלה על ידי משתמש גרמני מעיר ליד קלן בגרמניה. זה היה מספר מרסן הראשוני הראשון שנתגלה באופן בלתי רציף מאז 1988.
- ב-17 בספטמבר 2015 נשלחה ממחשבו של קורטיס קופר הודעה לשרת מיזם GIMPS על גילוי מספר מרסן הראשוני ה-49. אולם, בגלל באג תוכנתי, ההודעה לא התקבלה. כך נשאר מספר זה עלום עד עבודות התחזוקה השוטפות של השרת, כשלושה חודשים וחצי לאחר מכן. ב-7 בינואר 2016 הוכרז המספר באופן רשמי מאחר שתאריך הגילוי הקובע לפי המיזם, הוא היום בו הבחין בו לראשונה אדם. קביעה זו באה בעקבות המקרה שאירע ב-3 בנובמבר 1961. ביום זה קרא אלכסנדר הורביץ את תדפיס המחשב שלו מהסוף להתחלה (מאחר שזו הדרך שבה נערם. בדומה למדפסת המפיקה דו"ח מההתחלה לסוף כך שהדף הראשון של הדו"ח יימצא בתחתית הערמה) והבחין במספר מרסן הראשוני ה-20, מספר שניות לפני מספר מרסן הראשוני ה-19, , אף על פי שהמספר הקטן התגלה מוקדם יותר. מכאן ש- נחשב ל"מספר מרסן הראשוני שמעולם לא היה הגדול ביותר" כשהתגלה.[2]
GIMPS העניקו $50,000 למחלקה למתמטיקה של אוניברסיטת קליפורניה בלוס אנג'לס, $25,000 מיועדים לצדקה ורוב שאר הכסף יועבר למגלים של ששת מספרי מרסן הראשוניים האחרונים.
למגלי המספר הראשוני הראשון שלו לפחות מאה מיליון ספרות ממתין פרס בן $150,000 מטעם קרן החזית האלקטרונית.[3] למגלי המספר הראשוני הראשון שלו לפחות מיליארד ספרות ממתין פרס בן $250,000 מטעם קרן החזית האלקטרונית.[3]
רשימת מספרי מרסן ראשוניים
# | חזקה | מספר מרסן | מספר ספרות | תאריך גילוי | מגלה | שיטה |
---|---|---|---|---|---|---|
1 | 2 | 3 | 1 | 430 לפנה"ס | מתמטיקאים יווניים | חלוקה נסיונית |
2 | 3 | 7 | 1 | 430 לפנה"ס | מתמטיקאים יווניים | חלוקה נסיונית |
3 | 5 | 31 | 2 | 300 לפנה"ס | מתמטיקאים יווניים | חלוקה נסיונית |
4 | 7 | 127 | 3 | 300 לפנה"ס | מתמטיקאים יווניים | חלוקה נסיונית |
5 | 13 | 8191 | 4 | 1456 | אלמוני | חלוקה נסיונית |
6 | 17 | 131071 | 6 | 1588 | פייטרו קטלדי | חלוקה נסיונית |
7 | 19 | 524287 | 6 | 1588 | פייטרו קטלדי | חלוקה נסיונית |
8 | 31 | 2147483647 | 10 | 1772 | לאונרד אוילר | חלוקה נסיונית מתקדמת |
9 | 61 | 2305843009213693951 | 19 | נובמבר 1883 | איבן פרוושין | סדרת לוקאס |
10 | 89 | 618970019642…137449562111 | 27 | יוני 1911 | ראלף פאוורס | סדרת לוקאס |
11 | 107 | 162259276829…578010288127 | 33 | 1 ביוני 1914 | ראלף פאוורס | סדרת לוקאס |
12 | 127 | 170141183460…715884105727 | 39 | 10 בינואר 1876 | אדואר לוקאס | סדרת לוקאס |
13 | 521 | 686479766013…291115057151 | 157 | 30 בינואר 1952 | רפאל רובינזון | מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC |
14 | 607 | 531137992816…219031728127 | 183 | 30 בינואר 1952 | רפאל רובינזון | מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC |
15 | 1,279 | 104079321946…703168729087 | 386 | 25 ביוני 1952 | רפאל רובינזון | מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC |
16 | 2,203 | 147597991521…686697771007 | 664 | 7 באוקטובר 1952 | רפאל רובינזון | מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC |
17 | 2,281 | 446087557183…418132836351 | 687 | 9 באוקטובר 1952 | רפאל רובינזון | מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC |
18 | 3,217 | 259117086013…362909315071 | 969 | 8 בספטמבר 1957 | האנס רייזל | מבחן לוקאס-להמר למספרי מרסן / מחשב BESK |
19 | 4,253 | 190797007524…815350484991 | 1,281 | 3 בנובמבר 1961 | אלכסנדר הורביץ | מבחן לוקאס-להמר למספרי מרסן / מחשב IBM 7090 |
20 | 4,423 | 285542542228…902608580607 | 1,332 | 3 בנובמבר 1961 | אלכסנדר הורביץ | מבחן לוקאס-להמר למספרי מרסן / מחשב IBM 7090 |
21 | 9,689 | 478220278805…826225754111 | 2,917 | 11 במאי 1963 | דונלד גיליס | מבחן לוקאס-להמר למספרי מרסן / מחשב ILLIAC II |
22 | 9,941 | 346088282490…883789463551 | 2,993 | 16 במאי 1963 | דונלד גיליס | מבחן לוקאס-להמר למספרי מרסן / מחשב ILLIAC II |
23 | 11,213 | 281411201369…087696392191 | 3,376 | 2 ביוני 1963 | דונלד גיליס | מבחן לוקאס-להמר למספרי מרסן / מחשב ILLIAC II |
24 | 19,937 | 431542479738…030968041471 | 6,002 | 4 במרץ 1971 | בריינט טקרמן | מבחן לוקאס-להמר למספרי מרסן / מחשב IBM 360/91 |
25 | 21,701 | 448679166119…353511882751 | 6,533 | 30 באוקטובר 1978 | לנדון נול ולורה ניקל | מבחן לוקאס-להמר למספרי מרסן / מחשב CDC Cyber 174 |
26 | 23,209 | 402874115778…523779264511 | 6,987 | 9 בפברואר 1979 | לנדון נול | מבחן לוקאס-להמר למספרי מרסן / מחשב CDC Cyber 174 |
27 | 44,497 | 854509824303…961011228671 | 13,395 | 8 באפריל 1979 | הארי נלסון ודייוויד סלווינסקי | מבחן לוקאס-להמר למספרי מרסן / מחשב Cray 1 |
28 | 86,243 | 536927995502…209433438207 | 25,962 | 25 בספטמבר 1982 | דייוויד סלווינסקי | מבחן לוקאס-להמר למספרי מרסן / מחשב Cray 1 |
29 | 110,503 | 521928313341…083465515007 | 33,265 | 29 בינואר 1988 | וולטר קולקוויט ולוק וולש | מבחן לוקאס-להמר למספרי מרסן / מחשב NEC SX-2 |
30 | 132,049 | 512740276269…455730061311 | 39,751 | 19 בספטמבר 1983 | דייוויד סלווינסקי | מבחן לוקאס-להמר למספרי מרסן / מחשב Cray X-MP |
31 | 216,091 | 746093103064…103815528447 | 65,050 | 1 בספטמבר 1985 | דייוויד סלווינסקי | מבחן לוקאס-להמר למספרי מרסן / מחשב Cray X-MP/24 |
32 | 756,839 | 174135906820…328544677887 | 227,832 | 17 בפברואר 1992 | דייוויד סלווינסקי ופול גייג' | מבחן לוקאס-להמר למספרי מרסן. מחשב Cray-2 |
33 | 859,433 | 129498125604…243500142591 | 258,716 | 4 בינואר 1994 | דייוויד סלווינסקי ופול גייג' | מבחן לוקאס-להמר למספרי מרסן / מחשב Cray C90 |
34 | 1,257,787 | 412245773621…976089366527 | 378,632 | 3 בספטמבר 1996 | דייוויד סלווינסקי ופול גייג' | מבחן לוקאס-להמר למספרי מרסן / מחשב Cray T94 |
35 | 1,398,269 | 814717564412…868451315711 | 420,921 | 13 בנובמבר 1996 | GIMPS / ג'ואל ארמנגאוד | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 90 Pentium |
36 | 2,976,221 | 623340076248…743729201151 | 895,932 | 24 באוגוסט 1997 | GIMPS / גורדון ספנסר | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 /מחשב מגהרץ 100 Pentium |
37 | 3,021,377 | 127411683030…973024694271 | 909,526 | 27 בינואר 1998 | GIMPS / רולנד קלרקסון | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 200 Pentium |
38 | 6,972,593 | 437075744127…142924193791 | 2,098,960 | 1 ביוני 1999 | GIMPS / נאיאן הג'ראטוולא | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 350 Pentium 2 |
39 | 13,466,917 | 924947738006…470256259071 | 4,053,946 | 14 בנובמבר 2001 | GIMPS / מייקל קמרון | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 800 Athlon T-Bird |
40 | 20,996,011 | 125976895450…762855682047 | 6,320,430 | 17 בנובמבר 2003 | GIMPS / מייקל שאפר | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 /מחשב 2 גיגה-הרץ Dell Dimension |
41 | 24,036,583 | 299410429404…882733969407 | 7,235,733 | 15 במאי 2004 | GIMPS / ג'וש פינדלי | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2.4 גיגה-הרץ Pentium 4 |
42 | 25,964,951 | 122164630061…280577077247 | 7,816,230 | 18 בפברואר 2005 | GIMPS / מרטין נובאק | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2.4 גיגה-הרץ Pentium 4 |
43 | 30,402,457 | 315416475618…411652943871 | 9,152,052 | 15 בדצמבר 2005 | GIMPS / קורטיס קופר | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2 גיגה-הרץ Pentium 4 |
44 | 32,582,657 | 124575026015…154053967871 | 9,808,358 | 4 בספטמבר 2006 | GIMPS / קורטיס קופר וסטיבן בון | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 3 גיגה-הרץ Pentium 4 |
45 | 37,156,667 | 202254406890…022308220927 | 11,185,272 | 6 בספטמבר 2008 | GIMPS / האנס-מייקל אלוניץ' | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2.83 גיגה-הרץ Core 2 Duo |
46 | 42,643,801 | 169873516452…765562314751 | 12,837,064 | 12 באפריל 2009 | GIMPS / אוד סטרינדמו | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 3 גיגה-הרץ Core 2 Duo |
47 | 43,112,609 | 316470269330…166697152511 | 12,978,189 | 23 באוגוסט 2008 | GIMPS / אדסון סמית' | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 745 מגהרץ Dell Optiplex |
48 | 57,885,161 | 581887266232…071724285951 | 17,425,170 | 25 בינואר 2013 | GIMPS / קורטיס קופר | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 /מחשב 3 גיגה-הרץ Core 2 Duo |
49 | 74,207,281 | 300376418084…287190498687 | 22,338,618 | 7 בינואר 2016 | GIMPS / קורטיס קופר | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 Intel i7-4790 @ 3.60GHz |
50 | 77,232,917 | 467333183359…069762179071 | 23,249,425 | 26 בדצמבר 2017 | GIMPS / ג'ונתן פייס | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 Intel i5-6600 @ 3.30GHz |
51 | 82,589,933 | 325217902591…148894445742 | 24,862,048 | 7 בדצמבר 2018 | GIMPS / פטריק לארוץ' | מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 Intel i5-4590T @ 2.0GHz |
קישורים חיצוניים
- אתר האינטרנט הרשמי של GIMPS
הערות שוליים
- ^ GIMPS Milestones Report, www.mersenne.org
- ^ The Largest Known prime by Year: A Brief History, primes.utm.edu
- ^ 3.0 3.1 EFF Cooperative Computing Awards
32545826GIMPS