מחולל מספרים אקראיים
הכנות ובדיקות סטטיסטיות > מבחנים סטטיסטיים

קיים מגוון גדול של מבחנים סטטיסטיים לבדיקת איכות מחולל אקראי. המבחנים לא נועדו להוכיח מתמטית שהרצף שהמחולל מייצר אקראי, אלא לאתר נקודות תורפה במחולל שעשויות להעיד על אקראיות לקויה. הבדיקות נעשות על דגימה של הפלט בסיביות. כל מבחן סטטיסטי קובע האם הרצף הנדון מכיל מאפיינים מסוימים שנצפו מראש ברצף אקראי אמיתי. תוצאת מבחן או ניסוי כזה אינה דטרמיניסטית אלא הסתברותית. למשל רצף אקראי אמיתי אמור להכיל סיביות אפס ואחד במספר שווה בקירוב. אם הרצף הנדון אינו עונה על דרישה זו אפשר לומר שהמחולל שייצר את הרצף נכשל בניסוי. לעומת זאת אם מספר הסיביות אחד ואפס שווה בשיעור סטייה מסוים שנקבע מראש, אפשר לומר שהרצף האקראי "התקבל". במונח התקבל מתכוונים שאין דוחים את טענת אקראיותו. גם אם הרצף עובר בהצלחה מבחן סטטיסטי נתון, אין הדבר מהווה הוכחה מוחלטת לאקראיותו אלא יותר מעין אישוש הסתברותי.
רוב המבחנים הסטטיסטיים מבוססים על התפלגות נורמלית והתפלגות כי בריבוע ( \ \chi ^{2}). התפלגות נורמלית היא סכום מספר גדול של משתנים מקריים בלתי תלויים בעלי תוחלת ושונות זהים. משתנה מקרי  \ X הוא בעל התפלגות נורמלית אם פונקציית הצפיפות שלו היא מהצורה:
מסמנים זאת  \ X\sim N(\mu ,\sigma ^{2}). במקרה ש- \ X\sim N(0,1) מתקבלת התפלגות נורמלית "סטנדרטית" מהצורה:
הנקראת גם "עקומת הפעמון" בשל העובדה שגרף הפונקציה סימטרי ביחס לציר ה- \ y בכך מתקבלת צורת פעמון. המעבר מהתפלגות נורמלית של  \ X\sim N(\mu ,\sigma ^{2}) להתפלגות נורמלית סטנדרטית הוא  \ Z=(X-\mu )/\sigma .
התפלגות  \ \chi ^{2} עם  \ v דרגות חופש מתרחשת כאשר סוכמים ריבועי  \ v משתנים מקריים בלתי תלויים בעלי התפלגות נורמלית סטנדרטית. ניתן להשתמש בהתפלגות  \ \chi ^{2} כדי לייצג את מידת ההתאמה בין תדירות אירועים שנצפו לבין התדירות המשוערת תחת הנחה (היפותזה) הסתברותית כלשהי. פונקציית הצפיפות של התפלגות כי בריבוע היא מהצורה:
אם  \ X הוא משתנה מקרי בעל התפלגות  \ \chi ^{2} עם  \ v דרגות חופש, אזי  \ P(X>x)=\alpha . במילים אחרות  \ \alpha  מייצג את ההסתברות ש- \ X יחרוג מהערך הצפוי בנקודה  \ x. קיימות טבלאות מוכנות של ערכי התפלגות כי בריבוע, שאפשר להשתמש בהן כמקור להשוואה. במקרה של התפלגות נורמלית סטנדרטית כאשר  \ X\sim N(0,1) אומרים שהמשתנה  \ Z=X^{2} הוא בעל התפלגות כי בריבוע עם דרגת חופש אחת.
ניסוי סטטיסטי הוא תהליך שבהתבסס על ערכים שנצפו במשתנה מקרי אחד או יותר, מאשש היפותזה סטטיסטית הנקראת השערת האפס (אותה מסמנים  \ H_{0}) המייצגת טענה בנוגע להתפלגות המשתנה או המשתנים בהתאם לרמת מובהקות  \ \alpha . רמת המובהקות מייצגת את ההסתברות שהשערת האפס תתקבל או תדחה (גם בניגוד לנכונותה). מצב שבו השערת האפס נדחית למרות היותה נכונה (כאשר ערך  \ \alpha  גבוה מדי) נקרא "טעות מסוג I". לעומתה, טעות מסוג II עלולה להתרחש כאשר רמת המובהקות נמוכה מדי, אז קיימת סכנה שהשערה תתקבל למרות היותה שגויה, דהיינו במקרה זה הרצף ייחשב כאקראי אף על פי שאינו כזה.
את הניסוי עורכים עם "נתון" סטטיסטי שהוא פונקציה של אלמנטים מהדגימה (כגון מספר האפסים או האחדים בדגימה). הנתון צריך להתאים להתפלגות הנורמלית או כי בריבוע של רצף אקראי אמיתי. את ערכי הנתון משווים עם ערכים ידועים מראש. לדוגמה אם  \ X מתאים להתפלגות כי בריבוע עם  \ v דרגות חופש וידוע שהנתון הסטטיסטי לצורך הניסוי אמור לקבל ערכים גבוהים יותר במקרה של אקראיות לקויה, קובעים ערך "סף"  \ x_{\alpha } לפי נתון ידוע מראש (בדרך כלל בעקבות ניסויים בערכים אקראיים אמיתיים) ומחשבים את  \ \alpha =P(X_{\alpha }), אם תוצאת הניסוי הנתון נמוכה מערך זה הרי שהרצף נכשל בבדיקה. בדרך דומה מחשבים את ערכי  \ \alpha  עבור כל ניסוי ספציפי ובודקים אם תוצאת הניסוי נמוכה מערך זה. אם בכל המקרים התוצאה גבוהה, אפשר לקבל את הרצף כאקראי. כמובן שיש להביא בחשבון אחוז נמוך של תוצאות, אפילו במקרה של רצף אקראי אמיתי שעלולות להיות נמוכות מערכי הסף שנקבעו, מה שמעיד כביכול על אקראיות לקויה. קביעת ערכי סף היא משימה קשה, ערכי סף בדרך כלל נקבעים אמפירית.
להלן מפורטים שישה מבחנים סטטיסטיים בסיסיים (המובאים בספר Handbook of Applied Cryptography).
במבחנים המתוארים  \ s=s_{0},s_{1},s_{2},...,s_{n-1} הוא סדרה של סיביות באורך  \ n. כאשר  \ n צריך להיות גדול, בין  \ 10^{3} ל- \ 10^{6} (מיליון סיביות). רמת המובהקות נקבעה כאן  \ \alpha =0.05 (ערכים אחרים אפשריים אך דורשים התאמות בערכי הסף). דוגמה לטבלת ערכים באחוזים של התפלגות נורמלית כצפוי מהתנהגות משתנים אקראיים:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  \ \alpha  | 0.1 | 0.05 | 0.025 | 0.01 | 0.005 | 0.0025 | 0.001 | 0.0005 |
|  \ x | 1.2816 | 1.6449 | 1.9600 | 2.3263 | 2.5758 | 2.8070 | 3.0902 | 3.2905 |
למשל בכניסה  \ \alpha =0.05 והערך  \ x=1.6449, משמעות הדבר שאם  \ X בעל התפלגות נורמלית סטנדרטית אזי  \ X חורג מהערך  \ 1.6449 בנקודה זו בחמישה אחוז מהמקרים בקירוב.