בתשובה לאלון עמית, 16/12/06 8:15
 |
|
 |
||
|
||||
 |
ב. 1. הבעיה עם הכתיבה של ראמנוג'אן היתה שהיה לו פורמליזם מאוד אישי של כתיבה מתמטית (שלא כל כך "התיישב" עם המקובל), כך שהיה קשה מאוד לתרגם את נוסחאותיו לכתיבה המקובלת (שלא כמו הנסחאות שהבאת) והיה קשה להבין מה הוא בעצם טוען (מרכוס דה סוטוי מביא נסחת סכום טור בה רמנוג'ן רשם סכום מודולו מבלי שהיה סימון כלשהו, כך שבמבט ראשון הנוסחה נראית אבסורדית). מצד אחד זה מחזק את הטיעון שהיה דרוש גאון כמו הארדי כדי לשים לב שיש משהו בדפים שקיבל וגם כך זה נס שכך קרה. מצד השני עדיין אני מנחש שרמנוג'אן ידע למי הוא שולח את נוסחאותיו, שכן רק לאדם שעסק ממש באותם נושאים כמו רמנוג'אן היה סיכוי לנחש את שפתו המתמטית. ג. 2. זו לא ממש טענה מקורית של דה-סוטוי וההוכחות שלו משכנעות ביותר. יש שם מובאה של מתמטיקאי צרפתי מן השורה הראשונה בן התקופה, שפשוט מסרב אפילו להתיחס לעבודות מתמטיות בטענה שאין להן שום יישום מעשי. ושוב אני ממליץ על הספר (המלצתו של טל כהן דיון 2734 ). כמתמטיקאי אני מניח שיהיה לך קשה עם הנסיונות של המחבר להמחיש מושגים ה"מובנים מעצמם" לאיש המקצוע, לפעמים באופן די מגושם. אבל הפלוס הגדול הוא העושר של הרקע ההיסטורי (וההתלהבות). למשל בעניין צרפת וגרמניה אני בטוח שתשתכנע. דרך אגב, מסקרן אותי לדעת: מן הספר נותרתי עם הרושם שהוכחת משפט רימאן צריכה לקדם פיצוח של קודים מסוג ה-RSA. לי זה נראה קצת מרחיק לכת. נראה שדרושים הרבה מאוד אפסים של פונקציית הזטא כדי ל"נסח" את המספרים הראשוניים הגדולים, אחרת היה אפשר לעשות זאת באופן חישובי "מהיר". ואם אכן כך, במה תועיל מציאת נסחה כללית לביטוי/חישוב האפסים? |
 |
 |
 |
|
|
|
||
|
||||
|
תוכל להפנות למקום בספר שבו מדובר על RSA, ואולי להרחיב קצת כאן? אני לא מבין בנושא כלום, אבל כדי לפצח את RSA צריך בעיקר לדעת איך לבצע פירוק מהיר לגורמים. למצוא ראשוניים גדולים צריך כל מי שרוצה להצפין עם RSA, אבל אלגוריתם מהיר בשביל זה קיים כבר כיום, מבלי שיהיה צורך בנכונות השערת רימן. | |
|
|
|
|
|
||
|
||||
|
בפרק העשירי: פיצוח מספרים וצפנים. כפי שכתב טל דיון 2734 הספר אינו ספר מתמטיקה אלא ספר על ההיסטוריה של המתמטיקה ולא בטוח שהנסיון שם להסביר את האלגוריתם מילולית תוך שימוש מינימלי בביטויים מתמטיים ימצא חן בעיניך (הסברים כאלו לעיתים גם מתקשים לחצות את מחסום התרגום). הסבר תמציתי שלא בורח מביטויים יש ב"סודות ההצפנה" של סיימון סינג בנספח י: המתמטיקה של צופן RSA. לגבי ההרחבה, אני ממש לא הכתובת כי אני חובבן מתמטי לחלוטין. אני יכול רק לצטט את ההסבר הציורי של סינג בסודות ההצפנה: א. יסוד הצופן הוא במנגנון המפתחות הציבוריים של דיפי-הלמן: נניח שא(ני) רוצה לשלוח לב(נק) את מספר האשראי שלי באופן בטוח. הבנק מייצר עבורי קופסת מטמון קטנה בעלת 2 מפתחות, מפתח נועל ומפתח פותח. הבנק שולח לי את הקופסה עם המפתח הנועל (e- מספר ההצפנה). אני שם פתק עם מספר האשראי שלי בקופסה, נועל אותה ושולח לבנק. הבנק הוא היחיד שיכול לפתוח את הקופסה כי רק ברשותו יש את המפתח הפותח. כלומר א' וכל העולם יכולים להצפין, אבל רק ב יכול לפענח. ב. איך מממשים מפתחות חד כיווניים כאלו במתמטיקה? בוחרים פונקציה פשוטה שהיפוכה קשה מאוד. דוגמה פשוטה ולא מקרית היא העלאה בחזקה מודולו. נניח שמספר האשראי שלי הוא 7. אני מעלה אותו בחזקת E=3 (מעין מספר ההצפנה) מודולו N=31 , התוצאה היא 2. כעת אני יכול למסור לך את התוצאה (2), את מספר ההצפנה (3) ואת המפתח הציבורי (31) ועדיין יהיה לך קשה לשחזר את ה-7 המקורי. ג. למזלך יהיה קשה, אך לא בלתי אפשרי (אתה צריך רק לבדוק הרבה פחות מ-31 אפשרויות). RSA השתמשו במשפט פרמה-אוילר (הרחבה של משפט פרמה הקטן) כדי להציע מפתחות חד כיווניים קצת יותר בטוחים. המשפט מבטיח ש-mod(X^(ed),N)=X כאשר ed=(p-1)*(q-1)+1, N=p*q ו-p,q ראשוניים. כעת הבנק בוחר p,q גדולים ובעזרתם מחשב ומפרסם את המפתח הציבורי N, את מספר ההצפנה e ומשאיר לעצמו את d בתור המפתח המפענח. אני מעלה את המספר שלי בחזקת e מוד N ושולח את הצופן לבנק. הבנק רק צריך להעלות את הצופן בחזקת d כדי לחשוף את הקוד המקורי. ד. כפי שאמרת, הסודיות של ההצפנה נסמכת על הקושי שבפירוק N ל-p*q ראשוניים. לו היה זה קל, כל האקר היה יכול לשחזר את התהליך. למזלם של המשתמשים אין אלגוריתם מהיר מספיק כדי לעשות זאת עבור ראשוניים גדולים מספיק. אם הבנתי נכון את דה-סוטוי הרי שהאפסים של פונקציית רימאן קשורים איכשהו לחישוב - (pi(N - מספר המספרים הראשוניים הקטנים מ-N, כך שהקשר בין השערת רימאן לפרוק לגורמים ראשוניים נראה לי רחוק מאוד. |
|
|
|
|
|
|
||
|
||||
|
תודה על השיעור המעניין, אבל אני כבר מכיר את החומר הזה (מספרו הנחמד של סינג וממקורות אחרים). התהיה שלי הייתה על הקשר של השערת רימן לכל זה - קשר שככל הידוע לי (וכאמור, אני לא מבין בזה כלום) אינו קיים. אני אעיף מבט בספר של דה-סוטוי בהזדמנות הקרובה ואראה איך הוא מציג את זה (מכיוון שהוא מתמטיקאי, אני מניח שהוא לא יגיד דברים לא נכונים). אגב, שים לב שהבעיה של "היפוך העלאה בחזקה מודולו" זה לא בדיוק מה ש-RSA משתמשים בו. הבעיה הזו נקראת "לוגריתם דיסקרטי", וגם היא בפני עצמה משמשת כבסיס למספר שיטות הצפנה ציבוריות. הפואנטה של RSA היא שקשה לחשב את d אם ידועים רק e ו-N. את d קל מאוד לחשב מתוך e אם ידוע מה שמכונה "פונקצית אוילר" של N, אבל הבעיה היא שהדרך הקלה ביותר שמכירים למציאת הערך שלה ב-N הוא על ידי פירוק N לגורמים (השאלה המעניינת היא האם יכולה להיות בתיאוריה דרך קלה יותר - עד כמה שידוע לי, אין תשובה כיום לשאלה הזו). |
|
|
|
|
|
|
||
|
||||
|
לשאלתך האחרונה: הרבה מהפרסומים הפופולריים על השערת רימאן מנסים לעשות לה נפשות בקרב ההדיוטות ע"י קשירתה לשבירת צפנים ציבוריים, וחבל שגם דו-סוטוי נופל בפח הזה. חיפוש מהיר מעלה כותרת אופיינית: http://www.guardian.co.uk/uk_news/story/0,3604,12987... התחושה שלך שזה מרחיק לכת היא נכונה - אין שום סיבה להניח שהוכחת השערת-רימאן תשנה ולו בפסיק את בטיחותן של שיטות ההצפנה הציבורית המקובלות. אם מישהו חושב שיש בידיו אלגוריתם יעיל לפירוק מספרים ראשוניים תחת הנחת השערת רימאן, הוא מוזמן לממש אותו כבר עכשיו - אני מוכן לערוב לו שהוא יפעל באותה מידה של הצלחה יום לפני ויום אחרי פרסום ההוכחה."if... somebody really has cracked the so-called Riemann hypothesis, financial disaster might follow. " (ייתכן, עקרונית, שההוכחה עצמה תוסיף כל כך הרבה ידע להבנתנו מספרים ראשוניים שמשהו באמת ישתנה. זה נשמע לי מאוד, מאוד לא סביר, ובכל מקרה הוכחה כזו תהיה הרבה יותר מהוכחת השערת-רימאן "גרידא"). |
|
|
|
|
|
|
||
|
||||
|
<ניטפוק אידיוטי> אלגוריתם לפירוק מספרים ראשוניים באמת נשמע כמו סנסציה... </ניטפוק אידיוטי> | |
|
|
|
|
|
||
|
||||
|
אוף. טל, מה התעריף לתיקון תגובות בדיעבד? | |
|
|
|
|
|
||
|
||||
|
קראתי את הספר ולזכותו של דה -סוטוי שסוחף אותך לקריאה מרתקת אבל כפי שנכתב ובמיוחד בחלק השני יש עומס של פרוט על הגרף של רימן וכמו שנכתב זה די מגושם ומייגע. אבל הכיסוי ההיסטורי,מכפר במידה על ליקוי זה ואני בא מתחום ההנדסה והכשרת מורים למתמטיקה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |