Header

  • עברית
  • English
  • العربية
  • Moodle
  • You Tube
  • facebook
  • GeoGebra
בית
  • אודות
    • חזון ומטרות מכון דוידסון
    • וויליאם (ביל) דוידסון
    • איך מגיעים?
    • חברי ההנהלה
    • חברי הוועד המנהל
    • עובדי מכון דוידסון
    • דרושים לדוידסון
    • כפר הנוער ע"ש לאוב
    • תמכו בנו
  • פעילויות
    • חוגים
    • מחנות מדע ומשלחות לחול
    • תוכניות למצטיינים
    • קידום והעצמת תלמידים
    • תוכניות מדעיות לכיתות
    • הרצאות, כנסים ואירועים
    • תחרויות
    • מורים − השתלמויות ותמיכה
    • תוכניות מתוקשבות
    • פעילויות החודש במכון דוידסון
  • דוידסון Online
    • שאל את המומחה
    • מאגר מדע: סרטונים וכתבות
    • המעגל המתמטי
    • אפליקציות ויישומוני מדע
    • ניסויי מדע בבית
    • חדר מורים
    • כל מה שרציתם לדעת על המוח
  • גן המדע
    • מידע למגיעים למוזיאון
    • חוגגים איתנו בגן המדע
    • פעילויות לגנים ולבתי ספר
    • פעילויות לארגונים ולקבוצות
    • מוצגים בגן
    • סדנאות "מדעכיף" בפסח
    • רעש וצלצולים בגן המדע
  • פר"ח

דוידסון Online
  • שאל את המומחה
  • מאגר מדע: סרטונים וכתבות
  • המעגל המתמטי
    • פורום חידות סקובידו
    • כתבות
    • סרטונים
    • שעשועים מתמטיים
    • פורום פתוח
    • סיפורי ד"ר לא
    • בלוגריתמוס מתמטי
  • אפליקציות ויישומוני מדע
  • ניסויי מדע בבית
  • חדר מורים
  • כל מה שרציתם לדעת על המוח

חפשו פעילויות וכתבות

מה חדש בדוידסון Online

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

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

שתף

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

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

מספר ראשוני הוא מספר חיובי ושלם שאינו מתחלק בשום מספר חוץ מאחת וממנו עצמו. המספרים הראשוניים הקטנים ביותר הם 2, 3, 5, 7, 11, 13, 17. הגדרת המספרים הראשוניים קלה ופשוטה להבנה, אבל אל תיתנו לזה להטעות אתכם. הם נושא סבוך בעולם המחקר המתמטי, ועל אף הניסיונות הרבים לאפיין את המספרים הראשוניים, שאלות רבות נותרו פתוחות עד היום.

כבר בשנת 300 לפני הספירה הוכיח אוקלידס שיש אינסוף מספרים ראשוניים, אך ככל שהמספרים גדלים שכיחותם של המספרים הראשוניים יורדת. כך, למשל, עד 1,000 יש 168 מספרים ראשוניים, אך בין 1,000 ל-2,000 המספר יורד ל-135 מספרים ראשוניים. עד כה לא נמצאה תבנית ייחודית שתאפיין מתי מופיעים מספרים ראשוניים בסדר המספרים הכללי, לכן הם נחשבים אקראיים.

אחד הדברים הידועים לגבי המספרים הראשוניים הוא שמלבד 2 ו-5, כולם מסתיימים בספרות 1, 3, 7 ו-9. אם ההנחה שהמספרים הראשוניים מופיעים בצורה אקראית נכונה, נצפה שהמספר הבא בסדרת המספרים הראשוניים יסתיים בסיכוי זהה (25%) בכל אחת מארבע הספרות האלה. זה בדיוק מה שבדקו צמד החוקרים שהגישו את ממצאיהםלאחרונה לכתב העת המדעי Nature. הם בדקו במחקר יותר ממיליארד מספרים ראשוניים, וגילו חריגה מההתפלגות הזאת. אם יש מספר ראשוני המסתיים ב-1, רק ב-18 אחוז מהמקרים גם המספר הראשוני הבא יסתיים ב-1. לעומת זאת, 30 אחוז מהמספרים הראשוניים אחרי מספר המסתיים ב-1 יסתיימו ב-3 או ב-7, ורק 22 אחוז יסתיימו בספרה 9. כלומר, מספרים ראשוניים המסתיימים בספרה 1 נוטים שלא להופיע לפני מספרים המסתיימים באותה ספרה. תוצאות דומות התקבלו בעבור מספרים המסתיימים ב-3, 7 ו-9.

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

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

איך זה עובד?

נניח שמרדכי רוצה לשלוח מידע מוצפן לאסתר. שניהם צריכים להסכים מראש על פונקציה שקל מאוד להפעילה על מספר מסוים אך קשה לשחזר את המספר לאחר שהפעולה נעשתה. במקרה של RSAהפונקציה היא xy mod N. הפונקציה modהיא חישוב השארית השלמה בפעולת חילוק, למשל: 5 mod 4 = 1, כלומר אחרי שמחלקים 5/4 השארית היא 1.

אסתר בוחרת שני מספרים ראשוניים, המכונים לצורכי נוחות pו-q, ומכפילה אותם זה בזה. התוצאה היא N. לדוגמה, 13x23=299. עכשיו אסתר מייצרת מספר נוסף, מהנוסחה הפשוטה: (p-1)x(q-1)=1. במקרה שלנו התוצאה היא 265 =12x22+1. נפלאות המתמטיקה קובעות שכל מספר שאינו ראשוני הוא מכפלה של מספרים ראשוניים, שניים או יותר. במספר כמו 265 אפשר לחשב די בקלות את הגורמים המרכיבים אותו, 5x53. אפשר גם להיעזר במחשבון פירוק לגורמים. לשני הגורמים האלה, אסתר קוראת rו-s. עכשיו הכול מוכן, ואסתר מפרסמת את המפתח הפומבי שלה להצפנה, שהוא המספר Nואחד משני הגורמים שחישבה. הגורם השני ידוע אך ורק לה, בדוגמה שלנו: N=299, r=53.

כשמרדכי רוצה לשלוח לאסתר מספר מוצפן, הוא משתמש בפונקציה המוסכמת. נניח שהוא רוצה לשלוח לה את הציון שקיבלה מאחשוורוש, 10. הוא מציב אותו במקוםx  בפונקציה,xy mod N, ומשתמש בשני המספרים הפומביים שפרסמה אסתר ובמחשבון מדעי פשוט.1053 mod 299=43  . את המספר 43 הוא שולח לאסתר, וגם אם המן במקרה יתפוס את השליח, המספר לא יאמר לו דבר. אסתר, לעומת זאת, לוקחת את המספר שקיבלה ממרדכי, מציבה אותו בפונקציה עם המתפח הפרטי שלה ומקבלת את המספר שהצפין מרדכי: 435 mod 299 = 10. אתם יכולים לנסות את זה בעצמכם.

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

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

 

מירי אדלר, דוקטורנטית במכון ויצמן למדע



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

  • This article has 2 comments
  • 23.03.16

תגובות

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

הוגש ע"י הפ ב־ג', 29.03.2016 , 12:27.

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

  • השב
  • אשכול המלא

האם הנוסחא שגויה?

הוגש ע"י עינת ב־ב', 28.03.2016 , 10:40.

תודה על עוד כתבה מעניינת!
בדקו בבקשה את הנוסחא שהכנסתם לחישוב ״המספר הנוסף״.
ציינתם שהנוסחה היא (p-1) כפול (q-1) שווה אחד, כשבפועל האם הכוונה היא לא ל-
(p-1)x(q-1)+1 שווה המספר הנוסף?

  • השב
  • אשכול המלא

פרסום תגובה חדשה

ערך מאפיין זה ישאר פרטי ולא יוצג באופן ציבורי.
Image CAPTCHA
נא הקלד את התווים הנראים בתמונה זו
הדפס
CodeOasis
  • דף הבית
  • אודות
  • תוכניות
  • דוידסון Online
  • גן המדע
  • פר"ח
  • תנאי שימוש
  • RSS
כל הזכויות שמורות למכון דוידסון לחינוך מדעי ליד מכון ויצמן למדע (ע"ר)