?ונוה לכ תא סטייג ליב דבאי םאה

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

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

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

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

הז רוט לש ומוכס עיגמ םיגאב n רחאל .יסדנה רוטב תולדג סטייג ליב לש ויתומורת
ירה ,רוטה לש םינושארה וירביאב םיעיפומה םיעונצה םימוכסה ףרח .רלוד 2ⁿ-1 -ל
רמולכ ,סטייג ליב לש יתלחתהה ונוה תא רוטה םוכס רובעי םיגאב 40 רחאל רבכ
,הפ-לעב ריהמ בושיחב םג וז האצותל עיגהל לק .רלוד ןוילירטמ לודג היהי רוטה םוכס
.2⁴⁰ > 10¹² ןכלו ,2¹⁰ = 1024 > 10³ ,עודיכ ,ירהש ,ןובשחמב תועייתסה אלל

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

יונאה ילדגמ

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

תנשב הרבוח הדגאה .התאירקמ רעשל ןתינש יפכ הקיתע הכ הניא וז תיגולותימ הדגא
תחת המסרופו ,(Edouard Lucas) סאקול דראודא יתפרצה יאקיטמתמה ידי-לע ,1883
ץפוה הדגאה םע דחי .ירוקמה םשה לש םרגנא אוהש ,"סואלק 'פורפ" יודבה םשה
תניחבמ ןה ,הדגאה לש םצמוצמ לדומ הוויה רשא "יונאה ילדגמ" םשב עוצעצ תפרצב
הז קחשמ ץופנ זאמ .םלגה רמוח ריחמ תניחבמ ןהו (דבלב הנומש) תויקסידה רפסמ
םיפלק הנומש תועצמאב קחשמה לש קתוע תוריהמב רוציל ןתינ .תונווגמ תורוצב
.8 דעו 1-מ םירפסוממ

ךומנ הכ לדגמ ,הגאד לא) דבלב תויקסיד 4 והבוגש לדגמב ךילהתה לש המגוד הנה
.(םלועה לרוג לע עיפשמ וניא

יתמ ,טומל טוממ תחא תיקסיד הינש לכב םיריבעמ םירוסמהו םיליעיה םיריזנהש החנהב
?םלועה לע ץקה ץיקי

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

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

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

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

ירה ,תורבעה M תוצוחנ תויקסיד n-1 ןב לדגמ תרבעהל םאש עבונ םתירוגלאה רואתמ
תיקסיד קר שי ובש לדגמ תרבעהל .תורבעה 2M+1 תוצוחנ תויקסיד n ןב לדגמ תרבעהל
.תורבעה 2ⁿ-1 תוצוחנ תויקסיד n ןב לדגמ תרבעהל ןכלו ,תחא הרבעה הצוחנ תחא

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

ןסרמ ירפסמ

n רשאכ .תורבעה 2ⁿ-1 תוצוחנ תויקסיד n ןב לדגמ תרבעהל ,יונאה ילדגמ לש הדיחב
רשאכ .(2^u-1-ב קלחתמ 2^uv-1 זא n=uv םא) ינושאר וניא 2ⁿ-1 רפסמה םג ,ינושאר וניא
ןסרמ ןרמ םסרפ 1644 תנשב .ינושאר אוה 2ⁿ-1 רפסמה םגש ןכתיי ,ינושאר אוה n
רשאכ ינושאר אוה 2^p-1 רפסמה היפל הנעט ,המרפ לש ודידי ,(Marin Mersenne)
,ןסרמ .257-מ ןטקש רחא p לכל ינושאר וניאו p=2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257
.וז ותנעטל החכוה ןתנ אל ,המרפל המודב

דראודא חתיפ ךכ רחא הנש האמכ .ינושאר אוה 2³¹-1 רפסמהש רליוא חיכוה 1772 תנשב
.ןסרמ רפסמ לש ותוינושאר תקידבל הליעי הטיש ,יונאה ילדגמ לש הדיחה רבחמ ,סאקול
אוה 2¹²⁷-1 רפסמהש סאקול הארה ,י'צנוביפ תרדס לע הססבתהש ,וז הטיש תועצמאב
רחאל הנש 240-כ .ינושארכ עודיה רתויב לודגה רפסמה הז היה הנש 75 ךשמבו ,ינושאר
לש ותמישרב עיפומ וניאש ,2⁶¹-1 רפסמה :ןסרמ לש ותנעטב ןושאר םגפ הלגתה המוסרפ
.ינושארכ הלגתה ,ןסרמ

עיפומה ,2⁶⁷-1 רפסמהש לוק ןוסלנ קנרפ יאקירמאה יאקיטמתמה הארה 1903 תנשב
היטנ לעב הקיטמתמה לש ןוירוטסיה ,לב לפמט קירא .ינושאר וניא ,ןסרמ לש ותמישרב
:תיאקירמאה תיטמתמה הרבחה לש סנכב ותילגת תא לוק גיצה דציכ ראתמ ,היצזיטמרדל
לע בשיח הלמ רמול ילבו ,המבל הלע ,םילימב טעממש ימכ עודי היה דימתש ,לוק"  
:תורפס 21 ובו רפסמ לביקו ,1 תוריהזב תיחפה האצותהמ .2⁶⁷ רפסמה תא חולה  
הלפכמה תא בשיח םשו חולה לש רחאה ודיצל רבע לוק .147,573,952,589,676,412,927  
םיניזאמה להק .תוהז ואצמנ םיבושיחה ינש תואצות .193,707,721 X 761,838,257,287  
ילב ומוקמל רזח לוק .תורעוס םייפכ תואיחמב ,הז דסומ תודלותב הנושארל ,ץרפ  
".תולאש ויה אל להקב שיאל .ויפמ הגה איצוהל  

רפסמה םגש ררבתהו ,ןסרמ לש ותמישרב םירסחש םירפסמ ינש דוע ולגתה ךשמהב
ותנעטב ולגתנש תויועטה שמח ףרח .ינושאר וניא ,ןסרמ לש ותמישרב עיפומה ,2²⁵⁷-1
דחוימ ןיינע םילגמ ונאו ,ןסרמ ירפסמ םייורק 2ⁿ-1 הרוצהמ םירפסמ ,ןסרמ לש
ותנעטב םיעיפומש הלא ומכ ,םילודג םירפסמ לש תוינושאר תקידב .םהבש םיינושארב
רמולכ ,הנעטה תקידב המייתסה 1947 תנשב קר ןכלו ,םיבר םיבושיח הכירצמ ,ןסרמ לש
םוימ ,ןכ םא ,ופלח הנש תואמ שולש .p < 257 םהבש ןסרמ ירפסמ לכ לש םתקידב
לש ותיזחת תמועל רצק הז ןמז ךא ,התקידב המייתסנש דעו ותנעט תא ןסרמ הלעהש
לכ קיפסי אל ,ינושאר אוה תורפס 20 וא 15 ןב רפסמ םאה עובקל ידכ" :רמאש ,ןסרמ
."םלועבש ןמזה

ןסרמ ירפסמ 39 םיעודי תעכו ,בשחמה םתרנ םיינושאר ןסרמ ירפסמ רחא ץורימל
ןסרמ ירפסמ ףוסניא שי םאה ?םיינושאר ןסרמ ירפסמ ףוסניא שי םאה .םיינושאר
.ןיידע תועודי ןניא הלא תולאשל תובושתה ?םיינושאר םניאש

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

ןודרוג ,רפסמה הלגמ .2^2976221-1 אוה ,1997 תנשב הלגתהש ,המישרב 36-ה רפסמה
.וז המישמ לע םוי 15 ךשמב דבעש 100 םויטנפ בשחמב קפתסה ,38 ןב יאקירמא ,סנפס
19 ןב טנדוטס ,ןוסקראלק דנאלור ידי-לע הלגתה ,2^3021377-1 ,37-ה ןסרמ רפסמ
.הינרופילק תטיסרבינואב

.הלאווטר'גאח ןאיאנ ידי-לע 1999 ינויב 1-ב הלגתה ,2^6972593 - 1 ,38-ה ןסרמ רפסמ
50,000 לש סרפב ואצומ תא הכזמ אוהו ,תוינורשע תורפס ןוילמ ינשמ רתוי שי הז רפסמב
התא המ .תוינורשע תורפס ןוילממ רתוי ובש ינושאר רפסמ אצמיש ןושארל חטבוהש רלוד
םג וז תרגסמב שי ?םיננולתמ םתא ,וקלוח רבכש םיסרפ לע םירופיסב וננמז תא זבזבמ
.םיכוזל םיכחמ ןיידעש רתוי םילודג םיסרפ
2004 יאמב 15-ב הלגתה ,2^24036583 - 1 ,הכ דע הלגתהש ןורחאה ,41-ה ןסרמ רפסמ
.לטאיסמ ילדניפ שו'ג ידי-לע

ןורתפב ?םיינושארה ןסרמ ירפסמ תמישרב אבה רפסמה והמ ,ןבומכ ,איה ןאכ ונתדיח
,ןסרמ ירפסמ רחא לודגה טנרטניאה ץורימל ףרטצהל םינמזומ םתא .דבל םכניא הדיחה
לש יונפה ןמזה לוצינ תועצמאב ,הכ דע םינורחאה ןסרמ ירפסמ תשולש ולגתה ובש
לע תססבתמ וז הרטמל תשמשמה תינכותה .וז המישמב םיפתתשמה םיבשחמ יפלא
1930 תנשב הללכושש יפכ ,ןסרמ רפסמ לש ותוינושאר תקידבל סאקול דראודא ותטיש
.(D.H. Lehmer) רמל .ה.ד ידיב