פנקס חד-פעמי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
מ ניסוח
שורה 50:
הסיבה לשימוש ב-XOR במקום פעולה בינארית אחרת כמו [[OR]] או [[AND]], נובעת מהעובדה ש-XOR משמר אקראיות. אפשר להוכיח זאת בכמה דרכים, אבל מספיק להתבונן בטבלת האמת של XOR ולראות שהיא מכילה בדיוק 50% אפס ו-50% אחד, לעומת הפעולות OR ו-AND בהן היחס הוא 1 ל-3. כלומר התפלגות התוצאות של פעולת חיבור סיביות מודולו 2 אחידה.
 
קל להבין זאת במקרה של סיבית בודדת. אם נתון [[משתנה מקרי]] <math>Y</math> מעל <math>\{0,1\}</math> בהתפלגות שאינה אחידה, כלומר הסיכויים שיתקבל "0" הם <math>p_0</math> והסיכויים שיתקבל "1" הם <math>p_1</math>, כאשר <math>p_0+p_1=1</math> וכן <math>p_0 \neq p_1</math> , ונניח שנתון משתנה מקרי בלתי תלוי <math>X</math> בהתפלגות אחידה (סיכויים של <math>1/2</math> לאפס או אחד כמו ב[[הטלת מטבע]]). אפשר לראות שההסתברות ש-<math>Z=X\oplus Y</math> שווה "0" שווה להסתברות ש-<math>(x,y)=(0,0)</math> ועוד ההסתברות ש-<math>(x,y)=(1,1)</math> (כי לפי טבלת האמת של XOR רק בשני מקרים אילואלו התוצאה תהיה אפס). במקרה הראשון למשל ההסתברות היא <math>p_0</math> כפול <math>1/2</math>. בחשבון פשוט יוצא אם כך ש-<math>\textstyle\frac{p_0}{2}+\frac{p_1}{2}=1/2</math>. כלומר לא משנה מה הייתה ההתפלגות של <math>Y</math> לפני ה-XOR עם <math>X</math> לפני ה-XOR, התוצאה <math>Z</math> תתפלג תמיד באופן אחיד.
 
==פנקס רב-פעמי==