ינושאר ןועש

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

גוז לכ לש םוכסה ןהבש תובקוע תועש שש ןה 4 ,3 ,2 ,1 ,12 ,11 תועשהש תוארל לק
,9 העשה תא וא 7 העשה תא םישל שי 4 העשה דיל .ינושאר רפסמ אוה תוכומס תועש
האיבמ וללה תויורשפאה תקידב .8 העשה תא וא 6 העשה תא םישל שי 11 העשה דילו
:תונורתפה ינשל

  

?הזכ ינושאר שי םאה

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

,םייעבטה םירפסמה תא ארב םיהולא" ,רקנורק דלופואל יאקיטמתמה לש וירבד חורב
ולמע ירפב ונתקמעה תדימב יולת אצמנש ןורתפה ,"םדאה לש ולמע ירפ אוה ראשה לכ
:"רפסמ" גשומל ןתינש תועמשמב רמולכ ,םדאה לש
רמולכ ,יעבט רפסמ איה ,ונתדיח לש רשקהב ,"רפסמ" גשומל הילאמ תנבומה תועמשמה
הרדסה ירביאמ דחא םא םגש םושמ ,הדיחל ןורתפ ןיא וז תרגסמב .יבויחו םלש רפסמ  
.ינושאר רפסמ הניא םתלפכמ ןכלו ,1 םניאש םירביא ינש הרדסב שי ןיידע ,1 אוה  
רוחבל לכונ ,(םיילילשו םייבויח) םימלשה םירפסמה תצובקל ונישופיח תא ביחרנ םא
היהת וזש ידכ .(תחאו תחא סונימ) 1 תאו -1 תא תשרדנה הרדסב םירביא ינשכ  
אוהש ,3 איה םירביאה תשולש תלפכמו ,-3 היהי ישילשה רביאה תינובשח הרדס  
.ינושאר רפסמ ןכא  
םיילנויצרה םירפסמה תצובקל םימלשה םירפסמה תצובקמ גורחל ונמצעל השרנ םא
.3 ינושארה רפסמה תא תנתונ הירביא תלפכמש ,2 ,1.5 ,1 :תפסונ הרדס אצמנ  
תשולש תא ליפכנ םא .תונורתפ ףוסניא לבקנ םיישממה תצובקב ןורתפה תא שפחנ םא
.1 האצותה תא לבקנ הזב הז     תינובשחה הרדסה ירביא  
:הרדסה תא לבקנו רפסמב וז הרדס ירביאמ דחא לכ ליפכנ p ינושאר רפסמ לכל  
אוה רתוי טושפ ןורתפ .p איה הירביא תלפכמש  
.p-ל איה ףא הווש הירביא תשולש תלפכמש , , , :העובקה הרדסה  
תצובקב ןורתפ שפחלו הנומתה תא םילשהל אלש רשפא יא ,םולה דע ונעגה םא
הרוצהמ רפסמ אוה ,הז גשומב שגפ םרטש ימל ,בכורמ רפסמ .םיבכורמה םירפסמה  
רידגנ p ינושאר רפסמ לכל . אוה i-ו םיישממ םירפסמ םה b-ו a רשאכ ,a+bi  
.p-ל הווש הירביא תלפכמש   תינובשחה הרדסה תא  

?ליגרתה המ

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

רפסמ תנתונ תחא הרפסב ותלפכהש תורפס שולש ןב רפסמ םיאור ונא לפכה תלועפב
תועצמאב תורפס שולש ןב רפסמ רוציל תויורשפא 4X4X4=64 שי .תורפס עברא ןב
םתלפכהש םירפסמה תא אוצמל שי הלא תויורשפא 64 ןיבמ .תוינושארה תורפסה עברא
.תוינושאר תורפס עברא ןב רפסמ ןתית תחא תינושאר הרפסב

.תינושאר הניאש הרפס שי התאצותבש םושמ תלספנ ,לשמל ,573 X 3=1719 תורשפאה
:תומיאתמ תויורשפא עברא קר שיש הלעמ תויורשפאה לכ תקידב

775 X 3 = 2325                
555 X 5 = 2775                
755 X 5 = 3775                
325 X 7 = 2275                

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

775                
33                
------                
2325                
2325                 
--------                
25575                

?םיינושארל ףוס שי םאה

םאה .'וכו ,11 ,7 ,5 ,3 ,2 םירפסמה איה םיינושארה םירפסמה תרדס לש התליחת
םרפסמש וא ,םיינושאר םירפסמ לש יפוס רפסמ קר שי רמולכ ,תמייתסמ וזה הרדסה
?יפוסניא

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

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

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

:םיינושארה םיאב הנה

.םיינושאר םירפסמ לש ,n ,יפוס רפסמ קר םייקש חיננ .הלילשה ךרדב חיכונ
.P₁, P₂, ... P_n :וללה םיינושארה םירפסמה תא ןמסנ
:םייקמה M רפסמה תא קודבנ
M = P₁ P₂ ... P_n+1
.1 סולפ וללה םיינושארה םירפסמה לכ תלפכמ אוה M רמולכ

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

הניא איה ךא ,RSA הנפצהה תטישב םישמתשמל תובוט תושדח תניחבב איה וז האצות
תטישב חתפמל ירה ,םיינושאר םירפסמ לש תיפוסניא תומכ שיש ףא .םתוא תקפסמ
תרגסמב ותושרל ודמעי םיינושאר המכ תעדל ןינועמ שמתשמה .רדגומו יפוס לדוג RSA
טפשמה .םיינושארה םירפסמה טפשמ ןתונ וז הלאשל הבושתה תא .ולש חתפמה לדוג
ילושב הרעה הדיעמ ךכ) הרשע-שמחה ןב סואג ידי-לע 1792 תנשב הנושארל חסונ
הז טפשמ .ןכמ רחאל הנש האמ קר תילמרופ החכוהל הכז ךא ,(ולש םימתירגולה חול
m / ln m -ל בוריקב הווש m ןותנ רפסממ םינטקה םיינושארה םירפסמה תומכש רמוא
ךכיפל שי טיב 512 לש חתפמ לדוגב .(m לש יעבטה םתירגולה אוה ln m)
.ולוכ םוקיב םימוטאה רפסממ הלודגה תומכ ,םיינושאר םירפסמ 10¹⁵⁰

םיינושאר םניאש םיבקוע םירפסמ 1000 אצמ

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

הלפכמה אוה ,לשמל ,4! .הזב הז n דע 1-מ םירפסמה לכ תלפכמ אוה (תרצע n) n!
.1234 = 24
םירפסמה ףלאמ דחא לכב תיראש אלל קלחתמ 1001! רפסמה ,וז הרדגהל םאתהב
:ןכלו ,1001 דע 2 םוחתבש
;ינושאר וניא רמולכ ,2-ב קלחתמ 1001!+2 רפסמה
;ינושאר וניא רמולכ ,3-ב קלחתמ 1001!+3 רפסמה
;ינושאר וניא רמולכ ,4-ב קלחתמ 1001!+4 רפסמה
.                
.                
.                
.ינושאר וניא רמולכ ,1001-ב קלחתמ 1001!+1001 רפסמה

1000 לש הרדס איה 1001!+2, 1001!+3, 1001!+4, ..., 1001!+1001 הרדסה ךכיפל
.םיינושאר םניאש םיבקוע םירפסמ

םיינושאר םניאש םירפסמ השולש דוע

.םיינושאר םירפסמ םה ,2¹⁶+1-ו 2⁸+1 ,2⁴+1 ,2²+1 ,2¹+1 םירפסמהש בל םש המרפ
2²ⁿ+1 הרוצהמ רפסמ לכש ,1640 תנשב ןסרמל חלשש בתכמב ,הרעשה הלעה תאז תובקעב
אוה 2³²+1 = 4,294,967,297 רפסמה םאה עובקל לגוסמ וניאש ףיסוה ךא ,ינושאר אוה
וניא רפסמהש תוזירזב תונעל רשפא תעכ .וז הלאשל הבושת התיה אל ןסרמל םג .ינושאר
שי ףסונב .ינושאר רפסמ לש הרדגהה יפ-לע תאז קודבת טושפש תינכות תועצמאב ,ינושאר
הארה ,ידמ רתוי ץמאתהל ילב .ינושאר וניא ןותנ רפסמש םיארמה ,רתוי םיריהמ םינחבמ
.םיינושאר םניא 1,000,343-ו 999,919 םירפסמהש

999,919 = 1,000,000 - 81 = 1,000² - 9² = (1,000 + 9) X (1,000 - 9)
.םהב קלחתמ 999,919-ש םירפסמ ינש ונאצמ רמולכ

1,000,343 = 1,000,000 + 343 = 100³ + 7³ = (100 + 7) X (100² - 100 X 7 + 7²)
.םהב קלחתמ 1,000,343-ש םירפסמ ינש ונאצמ רמולכ

המרפ התוא קחש

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

5² - 1 = 24
7² - 1 = 48
11² - 1 = 120
13² - 1 = 168
:ךכיפל איה ונתרעשה .24-ב תקלחתמ האצותהש הלא תונויסנ העבראב תוארל לק
.24-ב קלחתמ p² - 1 :םייקתמ 3-מ לודג p ינושאר רפסמ לכל

:וז הרעשה חיכונ
.p² - 1 = (p+1)(p-1)
,1 איה תיראשה םא .2 וא 1 תיראש ןתונ אוה 3-ב ותקולחב ןכלו ,ינושאר רפסמ אוה p
הלפכמהש רורב ןכל .3-ב קלחתמ p+1 זא 2 איה תיראשה םאו ,3-ב קלחתמ p-1 זא
.3-ב תקלחתמ (p+1)(p-1)
ןכלו ,םיבקוע םייגוז םירפסמ ינש םה p+1 ,p-1 םירפסמה ןכלו ,יגוזיא רפסמ אוה p
.8-ב תקלחתמ םתלפכמ רמולכ ,4-ב קלחתמ םהמ דחא
.24-ב תקלחתמ איה ןכלו ,8-בו 3-ב תקלחתמ (p+1)(p-1) הלפכמהש וניארה

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

:( b-ו a ןה ויתורפס) תורפס יתש ןב רפסמ
.ינושאר וניא ןכלו ,9 לש הלפכמ אוה שרפהה ,(10a + b) - (10b + a) = 9(a - b)

:תורפס שולש ןב רפסמ
.ינושאר וניא ןכלו ,99 לש הלפכמ אוה שרפהה ,(100a + 10b + c) - (100c + 10b + a) = 99(a - c)

:תורפס עברא ןב רפסמ
(1000a + 100b + 10c + d) - (1000d + 100c + 10b + a) = 9(111a + 10b - 10c - 111d)
.ינושאר וניא ןכלו ,9 לש הלפכמ אוה שרפהה

?םימואת םיינושאר םירפסמ לש יפוסניא רפסמ שי םאה

.2 קוידב אוה םהיניב שרפההש םיינושאר םירפסמ גוז םה םימואת םיינושאר םירפסמ
,{17,19} ,{11,13} ,{5,7} ,{3,5} תוגוזה איה םימואתה םיינושארה לש המישרה תליחת
רבכ .3617000552³⁹⁰²⁰1 םה תעכ םיעודיה רתויב םילודגה םימואתה םיינושארהו
לש יפוסניא רפסמ םג שי םאה .םיינושאר םירפסמ לש יפוסניא רפסמ שיש וניארה
?םימואת םיינושאר םירפסמ

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

"?םימואת םיינושאר םירפסמ לש יפוסניא רפסמ שי םאה" הלאשל הבושת תלבקל
רמולכ ,םימואתה םיינושארה לכ לש םייכפוהה לש םוכסה לש ותוסנכתה תלאש הקדבנ
,ףוסניאל רדבתמ רוטה היה ול .(1/3+1/5)+(1/5+1/7)+(1/11+1/13)+... רוטה לש ותוסנכתה
םוכסש (Brun) ןורב וגיו חיכוה 1919 תנשב .תיבויח ונתלאשל הבושתהש רורב היה
.ונתלאשל הבושת תאיצמב ונתוא םדקמ וניא הז רוט רמולכ ,יפוס רפסמ אוה רוטה
1994 תנשב .1.9021605... וכרעו ,"ןורב לש עובקה" והלגמ םש לע יורק רוטה םוכס
,רוטב םירביא דועו דוע תריבצ תועצמאב ,ןורב לש עובקה בושיחב ילסיינ סמות קסע
ענכתשה תכשוממ הקידב רחאל .תשבתשמ האצותה בושיחה תומדקתה ךלהמבש בל םשו
.עדונה "םויטנפה גב" הלגתה ךכו ,ישיאה בשחמה לש דבעמב םגפמ תעבונ הלקתהש