בתשובה לאביב י., 23/11/03 19:36
 |
|
 |
||
|
||||
 |
אוף עוזי השיג אותי. בכל מקרה, אני מתנדב לנסות (אם יהיה לי זמן בין עבודה לתרגילים) לפענח את מספרו של עוזי במקרה הצורך. |
 |
 |
 |
|
|
|
||
|
||||
|
אתה לא אמור לפענח (זה דורש הוצאת שורש מודולו N, וזו בעיה קשה כי N שלי הוא מספר גדול יחסית). אבל אם אחליט להציג את ההודעה המקורית, אפשר יהיה לבדוק בין-רגע שאני לא מרמה (על-ידי העלאה בריבוע, שאותה קל לבצע). | |
|
|
|
|
|
||
|
||||
|
אני חושב שיש לי שורש S. סתם שאוכל לבדוק את עצמי - מה מספר הספרות של שורש S ומה שלושת הספרות האחרונות? |
|
|
|
|
|
|
||
|
||||
|
תפחית מהמספר שקיבלת 2 בחזקת 950. (מכאן אני מניח שאורך השורש של S הוא - 285) אתה צריך לקבל מספר באורך זוגי, שמורכב מזוגות מספרים המייצגים אותיות (00 עד 22). בשלב הזה - אתה אמור לקבל משפט הגיוני. (לפי ההגיון של עוזי) |
|
|
|
|
|
|
||
|
||||
|
מאחר ולא השתמשת בpad אקראי (אלא פשוט הוספת להודעה 2 בחזקת משהו גדול), מי שיש לו ניחוש מהי ההודעה יכול לוודא את הניחוש. כמו כן בהחלט ייתכן שמחשב יכול לסרוק מספר ניחושים כאלה (בעזרת מילון/רשימת מלים נפוצות/רשימת מלים מתגובות שלך בעבר + מלים שהופיעו באתרים זרים בנושא) בזמן קצר יותר מאשר הוצאת שורש. לסיום שאלה מתמטית: האם אתה יודע אם העובדה ששמת את ה pad בספרות הגדולות יותר (לעומת הקטנות יותר) הופל את הבעיה ליותר קשה או קלה (או שזה לא משנה)? |
|
|
|
|
|
|
||
|
||||
|
כן. | |
|
|
|
|
|
||
|
||||
|
באופן עקרוני ידוע שהיכולת להוציא שורש מודולו N שקולה ליכולת לפרק את המספר. אני מודה שללא ריפוד אקראי, אפשר לפענח את ההודעה על-ידי ניחוש (היא לא ארוכה במיוחד). אם, בסופו של התהליך ההודעה קצרה יותר מהשורש של N, אז אפשר להוציא שורש מן הריבוע שלה בשיטה הרגילה (כאילו זה היה מספר ממשי). היכולת לעשות דברים כאלה וודאי שאינה שקולה לפירוק (פעם היו לומדים אותה בכתה ו'). לכן צריך לרפד בחלק העליון של ההודעה. |
|
|
|
|
|
|
||
|
||||
|
הנה אתר של מישהו שמצא דרך לפענח מספרים כאלה: מדובר בהשקעה חד פעמית של 10 מליון דולר בערך.(*) וכל פיענוח יקח שנה אחת בלבד. לזכותו יאמר שלפניו דובר על השקעה של 10 עד 100 מיליארד עבור אותן תוצאות. ------------ (*) בתנאי שלא יהיה תקלות בייצור ובזמן הריצה. |
|
|
|
|
|
|
||
|
||||
|
נו שוין. מי אני שאתוכח עם סיבוכיות מטורפת. נמתין (לנצח?) לשורש של עוזי ואז החיים יהיו קלים כפשטידה (בשביל זה יש ספריה ל-BIG-INTEGERS). | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |