שיחה:פרדוקס יום ההולדת

מתוך ויקיפדיה, האנציקלופדיה החופשית

[עריכה] שני דברים לא ברורים

1. למה לוותר על הסימון האסימפטוטי ולמה להמיר את החסם מלמעלה בקירוב שנכון רק כשהיחס בין m ו-n הוא קטן?
2. מה זה "מערך שיעור" בהקשר הזה?

גדי אלכסנדרוביץ' 01:17, 1 בדצמבר 2006 (IST)

כדאי לכתוב על התקפת יום הולדת הקריפטאנליטית. אולי משתמש:Yossiea ירצה. ‏Harel‏ • שיחה 01:19, 1 בדצמבר 2006 (IST)

כדאי גם לוודא שהקישור מופיע לא רק בדף השיחה של הערך הזה אלא גם בערך עצמו (כשהוא משולב בצורה נאותה בפסקה שכבר קיימת, ולא בתור "ראו גם"). גדי אלכסנדרוביץ' 01:25, 1 בדצמבר 2006 (IST)

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

כל מרחב שיכולות להיות בו התנגשויות רלוונטי להתקפה הזו - אבל אתה צודק שבעיקרון זה שימושי בעיקר לזיוף של הודעות עם אותו גיבוב. אשנה בערך. ‏Harel‏ • שיחה 01:39, 1 בדצמבר 2006 (IST)

אני לא בטוח שהבנתי (ואני שואל מסקרנות): למשל, בוא נניח שהצפנתי משהו בDES. כמקובל, יש לך את כתב הסתר והכתב הגלוי ואתה מנסה לגלות את המפתח. קיימת סכנה של "התנגשות" - מפתח אחר שמעביר את הכתב הגלוי לכתב הסתר. איך זה עוזר לך? אם כבר, אתה עשוי לגלות בגלל זה את המפתח הלא נכון. גדי אלכסנדרוביץ' 01:45, 1 בדצמבר 2006 (IST)

נגיד שאתה מצפין משהו ב-DES, ונגיד שאתה משתמש במפתח שאתה מגריל אקראית איכשהו במרחב המפתחות שהוא בגודל 56 ביט, במוד ECB. נגיד שאני קולט את כל ההודעות שלך. אז אני צריך לקלוט רק כ-2 בחזקת 28 הודעות עד שאקבל שתי הודעות שהוצפנו באותו מפתח. נכון ששתי הודעות על אותו מפתח זה עוד לא שבירה של המערכת, אבל זה יכול לתת לי מידע על המבנה של ההודעות שלך (נגיד, הודעות קבועות על העברות בנקאיות), איפה יש שדות שמשתנים, איפה לא, וכו'. ‏Harel‏ • שיחה 10:23, 1 בדצמבר 2006 (IST)

לגבי ההסבר השלישי (זמן ההמתנה) - לא מובן למה ההסתברויות באגף שמאל שוות לאקספוננטים בצד ימין. Noytza

הוספתי הסבר - ההסתברות שזמן ההמתנה עולה על m שווה בדיוק להסתברות ש- m הכדורים הראשונים אינם מתנגשים, וזו חושבה בחלק השני. עוזי ו. 13:51, 1 בדצמבר 2006 (IST)

לשתי השאלות שלמעלה אני מוסיף כעת שלישית - למה הורדת את השורה שכתב הראל? היא שגויה? גדי אלכסנדרוביץ' 14:27, 1 בדצמבר 2006 (IST)

1. הסימון האסימפטוטי נראה לי מיותר. את החישוב המקורב אפשר להחליף בחזרה בחסמים (צריך להבהיר שזה קירוב ולא סתם חסם). 2. זו מעין בדיחה פרטית. לימדתי את הנושא הזה לא מזמן (בשני הקשרים רחוקים מאד: דגימה סטטיסטית ופירוק לגורמים ראשוניים). 3. לא נכון לצמצם את הרלוונטיות של הפרדוקס (בקריפטולוגיה) לפונקציות חד כיווניות בלבד. עוזי ו. 01:06, 3 בדצמבר 2006 (IST)

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

אני לא חושב שהנושא הזה קשור במיוחד לסימונים אסימפטוטיים (שאפשר להשתמש בהם בכל מקום). אבל זו לא סיבה שלא להוסיף את הזווית הזו, למשל כתת-סעיף של הסעיף על הסתברות החזרה. עוזי ו. 19:17, 3 בדצמבר 2006 (IST)

הסימון האסימפטוטי הוא סתם סימון, אבל המשמעות שלו בהקשר הזה נראית לי רחבה יותר ממה שמוצג עכשיו בערך. אני אנסה להוסיף את זה יותר מאוחר. גדי אלכסנדרוביץ' 19:49, 3 בדצמבר 2006 (IST)

בנוגע להתקפת יום ההולדת - ייתכן שהמקור לשאלה שלי בידע הקריפטוגרפי המצומצם שלי, אבל אני לא רואה כיצד ניתן לכתוב יותר מפסקה או שתיים על התקפה זו בלי לחזור על הכתוב בערך העוסק בפרדוקס. לדעתי עדיף להסתפק בתת סעיף בערך זה. יובל מדר 01:52, 3 בדצמבר 2006 (IST)