הצגת המקור של הדף "מחולל מספרים אקראיים"

[[קובץ:Roulette wheel.jpg|שמאל|ממוזער|250px|גלגל [[רולטה]], שיטה פרימיטיבית ליצירת מספרים אקראיים]]
ב[[חישוב (מדעי המחשב)|חישוביות]], '''מחולל מספרים אקראיים''' (מכונה בקיצור RNG, [[ראשי תיבות]] של המונח ה[[אנגלית|אנגלי]] Random number generator) הוא התקן פיזי או חישובי המייצר רצף סימנים (מספרים) חסרי תבנית או סדר דטרמיניסטי כלשהו, דהיינו [[אקראיות|אקראיים]]. מערכות מבוססות [[מחשב]] נפוצות יותר ביצירת מספרים אקראיים, אם כי לא תמיד איכותן טובה, אף על פי שרובן עוברות בהצלחה [[#מבחנים סטטיסטיים|מבחנים סטטיסטיים]] לוודא שאין להן דפוס קבוע כלשהו. קיים מגוון גדול של מקורות טבעיים להפקת מספרים אקראיים, חלקם היו ידועים מימי קדם וחלקם אמצעים חדשים כגון אלו המבוססים על [[מכניקה קוונטית]].

השיטות הפרימיטיביות ליצירת מספרים אקראיים – קרי [[קוביות משחק]], [[הטלת מטבע]], ערבוב [[קלף משחק|קלפים]], גלגל [[רולטה]] ומכונת [[לוטו]] – עדיין מצויות בשימוש כיום, בעיקר לצורך משחקי [[הימור]]ים. הן לא מתאימות כאשר נדרשת כמות גדולה של מספרים אקראיים באיכות גבוהה, כגון ב[[סטטיסטיקה]] מדעית או ב[[קריפטוגרפיה]], ובמיוחד לא נוחות ליישום במחשב. תופעות טבע שונות, כמו [[רעש (פיזיקה)|רעש]] תרמי, נראות על פניהן כאקראיות אמיתיות ויכולות לשמש כבסיס לחומרה ייעודית, אולם מרביתן סובלות מהטיה המקלקלת את אקראיותן, עובדה שנוצלה בעבר על ידי מהמרים, במיוחד במשחקי רולטה ו[[בלאק ג'ק]].

==שיטות פיזיקליות (חומרה)==
בהנחה שניתן להגדיר מספרים אקראיים, המקום הטוב ביותר למצוא אותם הוא בתופעות טבע או בתופעות [[כאוס|כאוטיות]]. [[חומרה]] ליצירת מספרים אקראיים היא מכשיר המתוכנן לנצל תופעות כאלה, דוגמת [[רעש תרמי]], [[רעש חשמלי]], [[האפקט הפוטואלקטרי]] או תופעות "קוונטיות" אחרות. אירועים אילו נחשבים תאורטית כבלתי צפויים לחלוטין, דבר שצריך להיבחן אמנם ביישום מעשי.

מכשיר טיפוסי כזה עשוי לכלול [[מגבר|רכיב הגברה]] שתפקידו להעביר את אירוע הטבעי ליחידה מיקרוסקופית ו[[מתמר]] שתפקידו להמיר את אירוע לאות [[דיגיטלי]]. בשיטות אחדות ממירים "מקור רעש" למחרוזת סיביות אקראית באמצעות התקן עצמאי המחובר למחשב. הרעש מוגבר, מסונן ומעובד לסיביות לפני העברתו דרך התקן אחר שנקרא [[קומפרטור]] (משווה) המייצר אות לוגי שמשנה מצבים, או שהאות הלוגי מועבר למחשב באמצעות [[RS-232]]. בגישה אחרת מנצלים התקן המובנה במרבית המחשבים המודרניים, ממיר [[דיגיטלי]]/[[אנלוגי]].

<!-- [[קובץ:Dice.jpg|שמאל|ממוזער|250px|שתי [[קוביית משחק|קוביות]] סטנדרטיות]] -->
[[קובץ:Lava lamp01.jpg|שמאל|ממוזער|100px|[[מנורת לבה]], הבועות מרחפות בנוזל בתנועות אקראיות]]
מכשירים אחרים מבוססים על אירועים מאקרוסקופיים כאוטיים כמו גלגל [[רולטה]]. אקראיותם נשענת על תאוריות בתחום [[מערכות דינמיות]] ו[[תורת הכאוס]], הטוענות שעל אף שאירועים אלו דטרמיניסטיים באופיים לפי חוקי ה[[מכניקה קלאסית|מכניקה הקלאסית]], במציאות מתרחשים באופן שלא ניתן לחיזוי משום שהם רגישים למשתנים סביבתיים ותנאים התחלתיים מורכבים ועדינים.

אירועים כאוטיים ניתנים להמרה לאות דיגיטלי באמצעים שונים. חברת [[סיליקון גרפיקס]] צילמה [[מנורת לבה|מנורות לבה]] כדי לייצר מהתמונות מספרים אקראיים. תאגיד RAND פיתחו מכשיר אלקטרוני המדמה גלגל רולטה כדי לייצר מספרים אקראיים. רעיונות אחרים הם לצלם בועות אוויר ב[[אקווריום]] או שמיים ביום מעונן ולהמיר את התמונות למחרוזת אקראית. [[קומודור 64]] [[מחשב אישי]] שהיה פופולרי בשנות השמונים הכיל מחולל חומרה שמוקם בכרטיס הקול והשתמש בהמרת [[אות אנלוגי]] ל[[אות דיגיטלי]] ליצירת מספרים אקראיים. היות שהתופעות הללו אינן נקיות מהטיות סטטיסטיות, מכשירים מתוחכמים יותר עשויים לנצל כמה מקורות ולבצע סינון של אותות בעלי תבנית קבועה או אותות המושפעים מתנאים חיצוניים כלשהם.

בכל מקרה, התוצאה של התקנים פיזיים כאלה אינה נקייה לחלוטין מהטיות סטטיסטיות. על פי רוב פלט מחולל כזה אינו אקראי לגמרי וסובל מהשפעות גורמים חיצוניים כמו [[מתח חשמלי]], [[שדה מגנטי|מגנטיות]], [[טמפרטורה]] או התיישנות. עקב כך אפשר בניתוח הסתברותי של הפלט לנחש מהי הסיבית הבאה ברצף בסיכויים גבוהים מחמישים אחוז בשיעור מסוים. על כן מקובל בדרך כלל לבצע תיקונים, אילו נעשים לאחר ייצור המספרים בחומרה המיוחדת לכך או באמצעות תוכנה.

===מקורות טבעיים===
להלן מספר מקורות טבעיים המאפשרים יצירת אקראיות אמיתית:
*[[רעש שוט]]; מקור רעש קוונטי ב[[מעגל חשמלי]]. דוגמה פשוטה היא [[דיודה פולטת אור|דיודת אור]], שבשל עקרון אי הוודאות פוטונים הנתקלים במעגל גורמים לשינויי מתח מקריים. מחשב Atari 8-bit השתמש בשיטה כזו.
*[[קרינה רדיואקטיבית]]; כמו זו המשמשת [[מערכת גילוי עשן|במערכות גילוי עשן]] מסוימות. הקרינה נמדדת באמצעות [[מונה גייגר]] המחובר ל[[מחשב]]. חברת [[HotBits]] מנצלת טכניקה כזו.
*[[פוטון|פוטונים]]; חלקיקי אור העוברים דרך [[מנסרה (אופטיקה)|מראה]] חצי שקופה. [[מוצר]] מסחרי של חברת [[id Quantique]] מבוסס על טכנולוגיה דומה.
*[[רעש תרמי]]; רעש הנובע מ[[נגד]] המוגבר באמצעות [[מגבר]] ליצירת [[מקור מתח]] אקראי. תופעות מסוג זה קלות ליישום ורגישות לטמפרטורה של המערכת. ומאותה סיבה פגיעות להתקפות ניסיון לשינוי טמפרטורת המכשיר.
*רעש מפולת; רעש הנוצר מ[[דיודת מפולת]] או מ[[דיודת זנר]].
*רעש אטמוספירי או [[רעש לבן]]; נמדד באמצעות [[מקלט רדיו|מקלט]] [[רדיו]] המחובר למחשב. חברת [[Random.org]] משתמשת בשיטה זו. פרטים על כיצד מנוצל הרעש לצורך מספרים אקראיים אפשר למצוא באתר החברה.
*[[מנורת לבה]]; טכניקה ידועה של צילום התנועה האקראית של בועות שעווה [[צמיגות]] במכל זכוכית ויצירת מספרים אקראיים מהתמונות. המחולל האקראי Lavarand של חברת סיליקון גרפיקס פעל בשיטה כזו.
*ערבוב פריימים של סרטי [[וידאו]] או תמונות של שמים ביום מעונן. חברת [[טכנולוגיות ליתיום]] האמריקאית השתמשה ב[[מצלמה]] קבועה שכוונה לשמים ביום מעונן כדי לייצר מספרים אקראיים.
*[[פיגור שעון]] (clock drift); תופעה הקיימת בשעונים כמו שעוני יד שנוטים לפגר או למהר לאחר זמן. הפרש הזמן הנמדד בין השעונים אינו קבוע ויכול לשמש כמקור לאקראיות. שעונים פועלים על [[מתנד אלקטרוני|מתנד]] קריסטלי או [[קוורץ]] המייצר אות חשמלי מחזורי. גרסה מסוימת של [[מרכזת]] [[אינטל]] כוללת התקן המנצל תופעה זו. המחולל מורכב משני מתנדים אחד מהיר והשני אטי ודיודה תרמית לאפנון המתנד האיטי שמפעיל בתורו מדידה של המתנד המהיר. פלט המדידות עובר דה-קורלציה לפני שהופך לרצף אקראי. על עיקרון דומה פועל מחולל חומרה המובנה במעבדי [[VIA Technologies]], גרסה אחת שלו פועלת על שילוב של ארבעה מתנדים במקצבים שונים. תוצאת [[XOR]] של שניים מהם משמשת להטיה של המתנד השלישי שבתורו משמש לשליטה במתנד הרביעי המייצר את הסיביות האקראיות. אקראיות מערכת מסוג זה מנצלת את העובדה ששינויים מינוריים במשתנים סביבתיים כמו טמפרטורה ומתח חשמלי משפיעה על קצב המתנדים ובכך מושגת [[אנטרופיה (סטטיסטיקה)|אנטרופיה]] גבוהה. קצב העבודה של מחוללים אילו גבוה, הפלט הגולמי מופק בקצב של עשרות מגה בית בשנייה והגישה אליהם מוגבלת ברמת משתמש כדי למנוע ניסיון לשלוט במחולל.

מרבית המכשירים המבוססים על התופעות המנויות בדרך כלל יקרים לייצור ותחזוקה, נוטים להיות אטיים מאוד ותוצאתם לא תמיד נקייה מנטייה סטטיסטית בשל רגישותם הרבה לתנאים סביבתיים ומשתנים חיצוניים. כיוון שכך, נוהגים למצוא פשרה סבירה בין אקראיות מושלמת הנובעת מחומרה ייעודית מחד ואקראיות אלגוריתמית (חישובית) מאידך, על ידי ניצול אנטרופיה זולה וזמינה. מרבית אפליקציות האבטחה מנצלות אנטרופיה טבעית שאפשר להפיק מהמערכת עצמה; אפליקציות מסוימות דורשות מהמשתמש לספק מחרוזת ארוכה של קואורדינטות עכבר או הקשות מקלדת אקראיות. [[אלגוריתם|אלגוריתמים]] אחרים דוגמת Yarrow משתמשים בטכניקה של איסוף נתונים אקראיים מגוונים לתוך "מאגר" (pool), שם הם מעובדים באמצעות פרימיטיבים קריפטוגרפיים כמו אלגוריתם הצפנה או פונקציית גיבוב, לפני שמופק פלט אקראי. בכך מושג שיפור באקראיות ללא צורך בחומרה יקרה. טכניקה זו פגיעה להתקפות קורלציה, היות שחלק מהנתונים הללו קל לניחוש. לא קשה למשל לנחש את נתוני שעון מערכת ששימשו לאתחול המחולל, אם ידוע טווח הזמן המשוער שבו התבצעה קריאה למחולל.

ספריית [[Cryptolib]] המכילה אוסף שגרות ספרייה קריפטוגרפיות בשפת [[C++]]&lrm;, מיישמת אלגוריתם הנקרא [[TrueRand]] ליצירת מספרים אקראיים המבוסס על רעיון ה[[מתנד אלקטרוני|מתנד]]. מרבית המעבדים המודרניים מכילים שני מתנדי גביש מובנים, אחד עבור שעון זמן אמת ואחד עבור שעון מעבד ראשי. אלגוריתם TrueRand מנצל עובדה זו, האלגוריתם משתמש בשרות (service) מערכת שעוצר את שעון זמן האמת. תת-שגרה אחת קובעת עצירה למשך קליק שעון אחד (1/60 של שנייה) בעוד שתת-שגרה אחרת נכנסת ללולאת המתנה. מאחר שהעצירה לא נמשכת בדיוק קליק שעון אחד, הסיבית הנמוכה ביותר של מונה הלולאה בין עצירה להפעלה של השעון השני, תהיה אקראית. בסביבה מרובת משימות אלגוריתם כזה עלול להיתקל בהשפעות לא אקראיות במקרה שמערכת ההפעלה תעצור את הלולאה הפנימית כדי לבצע מטלות אחרות.

== מחולל פסידו אקראי ==
{{ערך מורחב|מחולל מספרים פסידו-אקראיים}}

מחולל פסידו אקראי (PRNG) הוא אלגוריתם המסוגל לייצר כמות נכבדה של מספרים עם מאפייני אקראיות טובים באיכותם, אך לא אקראיים באמת ועל כן מכונים "מדומים". אחת השיטות הנפוצות להפקת מספרים פסידו אקראיים היא אלגוריתם linear congruential generator (בקיצור LCG) שמשתמש בנוסחת הנסיגה: <math>\ x_{n+1}=(aX_n+c)\mbox{ mod }m</math>. מחולל זה מייצר רצף מספרים פסידו אקראיים שגודלם אינו עולה על גודלו של <math>\ m</math> ומחזוריותו אינה גבוהה מ-<math>\ 2^m</math>. בשל פשטותו המחולל נמצא בשימוש נרחב כיום.

השיטה הראשונה והפשוטה ביותר ליצירת מספרים אקראיים (שיטת עט ונייר הנקראת "אמצע הריבוע") הומצאה ב-[[1946]] על ידי [[ג'ון פון נוימן]]. מעלים מספר בריבוע ונוטלים רק את הספרות האמצעיות כמספר אקראי וחוזר חלילה. השיטה אמנם קלה לביצוע אך איכותה ירודה. מרבית שפות התכנות כוללות פונקציות או שגרות [[ספרייה (תכנות)|ספריה]] התומכות ביצירת מספרים אקראיים כמו <math>\ \mbox{rand}()</math> ב[[שפת C]] (שמממשת ואריאציה של LCG). לעיתים הפונקציה מחזירה [[שבר עשרוני]] ב[[התפלגות אחידה רציפה|התפלגות אחידה]] בטווח <math>\ [0,1]</math> ולעיתים [[מספר שלם]]. מקובל שהפונקציה האקראית כוללת פונקציית עזר נוספת, המאפשרת למשתמש לאתחל את המחולל ממקור אקראי כלשהו במחשב, כמו מספר מילי השניות שחלפו מאז הפעלתו או נתוני מערכת (חסרי חשיבות) אחרים.

פונקציות ספריה סטנדרטיות לרוב בעלות מאפיינים סטטיסטיים גרועים וחלקן בעלי מחזוריות כה קצרה שאחרי כמה עשרות אלפי מספרים המחולל מתחיל לחזור על עצמו בהעתק מדויק. עבור יישומים פשוטים כמו משחקי מחשב הם מספקים אקראיות סבירה. כשמדובר במשחקי הימורים בסכומים גבוהים, בקריפטוגרפיה או בניתוחים סטטיסטיים מדעיים, לא מומלץ להשתמש בהם.

מהיבט של [[תורת האינפורמציה]], [[גרגורי צ'ייטין|צ'ייטין]] ו[[אנדריי קולמוגורוב|קולמוגורוב]] הוכיחו שרצף סיביות לא יקרא אקראי "אמיתי" אם יכול היה להיווצר על ידי תוכנת מחשב הקצרה ממנו. מחוללים פסידו אקראיים נפוצים אינם עומדים בדרישה זו. פלט המחולל בסיביות עולה לאין שיעור על אורכה של תוכנת המחשב המיישמת אותו. ישנן כמה הגדרות פורמליות לאקראיות, העדר תבנית או דפוס קבוע כלשהו ברצף האקראי או רמת אנטרופיה שלו (ראה [[דונלד קנות']]).

מעצם ההגדרה בהינתן האלגוריתם והמצב ההתחלתי, ניתן לשחזר במדויק את הרצף האקראי שהפיק המחולל. אפילו בהינתן מידע חלקי של מצב פנימי כלשהו של המחולל, עשוי הדבר להקל על ניחוש חלק או מלוא הרצף שהמחולל ייצר. בנוסף, היות שהמחולל מתחיל ממצב התחלתי בגודל סופי כלשהו וכמות הזיכרון אינה בלתי מוגבלת, בשלב כלשהו יחזור הרצף על עצמו שוב. אמנם המחוללים הנפוצים כיום מכילים מחזוריות עצומה, בסדר גודל של מיליוני סיביות. קיימת [[בעיה פתוחה במתמטיקה|שאלה פתוחה]] האם ניתן להבחין בהבדל בין פלט מחולל כזה לבין רצף אקראי אמיתי, ללא ידיעת המצב ההתחלתי והאלגוריתם. קריפטוגרפיה מסתמכת על ההשערה שלא ניתן לזהות הבדל כזה תוך שימוש ב[[עוצמת חישוב]] מוגבלת.

כיוון שהמחוללים הפסידו אקראיים הרגילים אינם מתאימים לצורך קריפטוגרפיה. לצד השיטות הרגילות, ברוב [[מערכת הפעלה|מערכות ההפעלה]] קיימות שגרות ספרייה יותר איכותיות ליצירת מספרים פסידו אקראיים המתאימות למטרות קריפטוגרפיות, כמו [[CryptGenRandom]] של [[מיקרוסופט]] או [[dev/random]] של [[לינוקס]].

==יישומים מעשיים==
אחד היישומים הראשונים ליצירת מספרים אקראיים היה כדורי [[פינג פונג]] ממוספרים שנופחו באוויר ונשלפו בדרך כלשהי ממכל ערבוב. טכניקה זו מגיעה לתוצאות טובות והיא בשימוש עד היום בעיקר בהגרלות [[לוטו]], בשיטה זו נעשה שימוש כבר על ידי הסינים כמאתיים שנה לפני הספירה במשחק הימורים שנקרא [[קנו (משחק)|קנו]]. חסרונה שהיא אטית מאוד ואינה מתאימה לתהליכים ממוכנים.

בעבר פרסמו חברות שונות ברשת ה[[אינטרנט]] רשימות של מספרים אקראיים שנלקחו ממקורות שונים. ב-1995 פרסם תאגיד RAND ספר המכיל רשימה של מיליון מספרים אקראיים שנוצרו באמצעות סימולציה אלקטרונית של גלגל רולטה שחובר למכונת [[כרטיס מנוקב|ניקוב]]. הרשימה הוכנה לאחר סינון ובדיקה קפדניים והייתה הראשונה מסוגה. עקב פרסומה ברבים רשימה זו לא מתאימה לצורך מפתחות הצפנה או גרעין התחלתי ל[[מחולל פסבדו אקראי קריפטוגרפי|מחולל פסידו אקראי קריפטוגרפי]], עיקר התועלת ברשימה כזו היה הדמיה לצורך מחקר מדעי.

השימושים העיקריים כיום במחוללים אקראיים הוא במשחקי הימורים למיניהם, במיוחד משחקי הימורים אלקטרוניים, דגימות סטטיסטיות, הדמיות מחשב ו[[משחקי מחשב]], [[סימולציה|סימולציות]] מדעיות וקריפטוגרפיה. ככלל תכונת האי-צפיות ([[אנטרופיה (סטטיסטיקה)|אנטרופיה]] גבוהה) חשובה בעיקר באפליקציות אבטחה, בהן מחולל מבוסס חומרה עדיף באופן כללי על פני מחולל פסידו אקראי, היכן שהדבר אפשרי. למשל השולח והמקבל יכולים לשחזר רצף אקראי מתוך גרעין התחלתי סודי המשותף להם ולהשתמש בו כמפתח הצפנה. [[צופן זרם|צופני זרם]] פועלים בדיוק בדרך זו.

מחוללי מספרים פסידו אקראיים מסייעים בפיתוח סימולציות ב[[שיטת מונטה קרלו]]. יתרונם בכך שהם מאפשרים לשחזר את הרצף האקראי שוב ושוב אם משתמשים באותו גרעין התחלתי.

מספרים אקראיים נפוצים בתכנות, בניגוד לקריפטוגרפיה הדורשת אקראיות באיכות גבוהה מאוד, למרבית היישומים דרושה בדרך כלל אקראיות בינונית. יישומים המציגים "טיפ יומי" אקראי, משחקי מחשב המדמים פעולות של יריב או יישומים המבצעים [[מיון (מדעי המחשב)|מיון]] ו[[אלגוריתם חיפוש|חיפוש]] ב[[מסד נתונים]], לא זקוקים לאקראיות באיכות גבוהה. מעבר לכך, נגני מדיה המאפשרים השמעת מוזיקה בסדר אקראי, דורשים בדרך כלל ששיר לא יחזור על עצמו פעמיים ברצף, דרישה שאינה הכרחית בהגדרה הבסיסית של אקראיות. יתרה מזו, מערכת אקראית אמיתית תאפשר מעצם ההגדרה חזרה של אלמנטים מסוימים מספר לא גדול של פעמים. אם ידוע שהמחולל אינו מייצר מספר אלמנטים עוקבים, מהווה הדבר פגם בסיסי.

==הכנות ובדיקות סטטיסטיות==
אפשר לייצר מספרים אקראיים באמצעות התקן המנצל תופעה פיזית ותיקון הטיות אם ישנן באמצעים שונים. היתרון הוא שהפלט במקרה זה ייקרא אקראי "אמיתי". אולם משיקולים מעשיים (כלכליים) הנטייה כיום היא להסתפק בתהליך חישובי דטרמיניסטי המייצר רצף מספרים ארוך שנראה על פניו כאקראי הנגזר ממקור אקראי אמיתי קצר, אותו מכנים פסידו-אקראי. אלגוריתם פסידו אקראי ידוע שנבדק היטב בעזרת מבחנים סטטיסטיים קפדניים מהווה חלופה זולה וסבירה. ארגוני תקינה בינלאומיים מפיצים תקנים שונים לבדיקת טיב מחוללים אקראיים ופסידו אקראיים.

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

הבעיה לקבוע האם מספר אקראי שיוצר באמצעות המחולל, הוא אקראי "אמיתי" היא בעיה מאוד קשה. גם אם יעבור בהצלחה מבחנים סטטיסטיים אין זה מוכיח שהרצף באמת אקראי. לצורך המחשה נתון הרצף האקראי הבא (40 סיביות):
: 11100 01100 01000 10100 11101 11100 10010 01001
אם נכפיל אותו 4 פעמים ו[[שרשור (מחרוזות)|נשרשר]] אותם למחרוזת אחת באורך 160 סיביות, כמובן שהתוצאה לא תהיה אקראית כלל. למרות זאת נראה שהמחרוזת האמורה תעבור בהצלחה מספר מבחנים סטטיסטיים. אם כי המחרוזת לא תעבור בדיקת אוטו-קורלציה, אפשר לראות כי המבחנים הסטטיסטיים אינם מספקים הוכחה וודאית לאקראיות.

===הלבנה (whitening)===
כמעט כל רצף אקראי גולמי שנוצר אם באמצעים פיזיים או באמצעים חישוביים, סובל מהטיה סטטיסטית וקורלציה. ישנן כמה דרכים לתיקון ההטיה מה שקרוי "הלבנה" בשל הזיקה ל[[רעש לבן]]. אפשר לתקן הטיות בחומרה בשלב ייצור המספרים, באמצעים טכניים או אלקטרוניים ואפשר לעשות זאת בשיטות חישוביות.

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

שיטה אחרת לתקן הטיה של רצף אקראי ולצמצם קורלציה היא לשלבו עם רצף אקראי אחר באיכות גבוהה, כמו חישוב XOR של הרצף האמור עם רצף פסידו אקראי קריפטוגרפי. התוצאה תהיה באיכות שאינה עולה על איכות הרצף הטוב מבין השניים.

דרך אחרת היא לשלב שני רצפים בעלי 'אקראיות חלשה' באמצעות XOR ולייצר מהם רצף אקראי באיכות גבוהה יותר. אם ההסתברות של סיבית אפס בשני הרצפים היא <math>\ 1/2 + e</math> כאשר <math>\ -1/2\le e\le 1/2</math> אזי <math>\ e</math> הוא ההטיה של הרצף. אם מחברים ב-XOR את שני הרצפים יחד מתקבל רצף בעל הטיה ל-<math>\ 2e^2</math>. אם חוזרים על הפעולה מספר פעמים עם רצפים אחרים מצמצמים את e יותר. עובדה זו נובעת מהתכונה של האופרטור XOR ו[[למת ההצטברות|לֶמת ההצטברות]].

המחוללים הקריפטוגרפיים משתמשים בפונקציית גיבוב קריפטוגרפית כמו [[SHA]] או [[MD5]] כדי לתקן הטיה וקורלציה. אפשר לנצל גם פונקציית [[קוד תיקון שגיאות|תיקון שגיאות]] (CRC) או אלגוריתם הצפנה. טכניקה זו אטרקטיבית מכמה סיבות, ראשית היא מהירה וקלה ליישום, שנית בתכנון מחולל קריפטוגרפי, משתדלים להסתמך על פרימיטיבים קריפטוגרפיים הקיימים במערכת ממילא, בכך חוסכים משאבים וזמן. איכות הפלט במקרה כזה תלויה לגמרי באיכות פונקציית הגיבוב או ההצפנה. שגם לאחר השימוש בהן תיתכן עדיין תאורטית הטיה קלה.

===מבחנים סטטיסטיים===
קיים מגוון גדול של מבחנים סטטיסטיים לבדיקת איכות מחולל אקראי. המבחנים לא נועדו להוכיח מתמטית שהרצף שהמחולל מייצר אקראי, אלא לאתר נקודות תורפה במחולל שעשויות להעיד על אקראיות לקויה. הבדיקות נעשות על דגימה של הפלט בסיביות. כל מבחן סטטיסטי קובע האם הרצף הנדון מכיל מאפיינים מסוימים שנצפו מראש ברצף אקראי אמיתי. תוצאת מבחן או ניסוי כזה אינה דטרמיניסטית אלא הסתברותית. למשל רצף אקראי אמיתי אמור להכיל סיביות אפס ואחד במספר שווה בקירוב. אם הרצף הנדון אינו עונה על דרישה זו אפשר לומר שהמחולל שייצר את הרצף נכשל בניסוי. לעומת זאת אם מספר הסיביות אחד ואפס שווה בשיעור סטייה מסוים שנקבע מראש, אפשר לומר שהרצף האקראי "התקבל". במונח התקבל מתכוונים שאין דוחים את טענת אקראיותו. גם אם הרצף עובר בהצלחה מבחן סטטיסטי נתון, אין הדבר מהווה הוכחה מוחלטת לאקראיותו אלא יותר מעין [[אישוש]] הסתברותי.

[[קובץ:distribution normal chi2.jpg|שמאל|ממוזער|250px]]
רוב המבחנים הסטטיסטיים מבוססים על [[התפלגות נורמלית]] ו[[התפלגות כי בריבוע]] (<math>\ \chi^2</math>). התפלגות נורמלית היא סכום מספר גדול של משתנים מקריים בלתי תלויים בעלי [[תוחלת]] ו[[שונות]] זהים. [[משתנה מקרי]] <math>\ X</math> הוא בעל התפלגות נורמלית אם [[פונקציית הצפיפות]] שלו היא מהצורה:
:<math>\ f(x)=\frac 1{\sigma\sqrt{2\pi}}\exp\left({\frac{-(x-\mu)^2}{2\sigma^2}}\right)</math>
מסמנים זאת <math>\ X\sim N(\mu,\sigma^2)</math>. במקרה ש-<math>\ X\sim N(0,1)</math> מתקבלת התפלגות נורמלית "סטנדרטית" מהצורה:
:<math>\ f(x) = \frac{1}{\sqrt{2\pi}} e^{-\frac{x^2}{2}} </math>
הנקראת גם "עקומת הפעמון" בשל העובדה שגרף הפונקציה סימטרי ביחס לציר ה-<math>\ y</math> בכך מתקבלת צורת פעמון. המעבר מהתפלגות נורמלית של <math>\ X\sim N(\mu,\sigma^2)</math> להתפלגות נורמלית סטנדרטית הוא <math>\ Z=(X-\mu)/\sigma</math>.

התפלגות <math>\ \chi^2</math> עם <math>\ v</math> דרגות חופש מתרחשת כאשר סוכמים ריבועי <math>\ v</math> משתנים מקריים בלתי תלויים בעלי התפלגות נורמלית סטנדרטית. ניתן להשתמש בהתפלגות <math>\ \chi^2</math> כדי לייצג את מידת ההתאמה בין תדירות אירועים שנצפו לבין התדירות המשוערת תחת הנחה (היפותזה) הסתברותית כלשהי. פונקציית הצפיפות של התפלגות כי בריבוע היא מהצורה:
: <math>\ f(x)=\frac{1}{\Gamma(v/2)2^{v/2}}x^{(v/2)-1}e^{-x/2}</math>, עבור <math>\ x</math> גדול מאפס והפונקציה <math>\ \Gamma(t)</math> נקראת [[פונקציית גמא]] המוגדרת: <math>\ \Gamma(t)=\int_0^\infty x^{t-1}e^{-x}dx</math> עבור <math>\ t</math> גדול מאפס.
אם <math>\ X</math> הוא משתנה מקרי בעל התפלגות <math>\ \chi^2</math> עם <math>\ v</math> דרגות חופש, אזי <math>\ P(X>x)=\alpha</math>. במילים אחרות <math>\ \alpha</math> מייצג את ההסתברות ש-<math>\ X</math> יחרוג מהערך הצפוי בנקודה <math>\ x</math>. קיימות טבלאות מוכנות של ערכי התפלגות כי בריבוע, שאפשר להשתמש בהן כמקור להשוואה. במקרה של התפלגות נורמלית סטנדרטית כאשר <math>\ X\sim N(0,1)</math> אומרים שהמשתנה <math>\ Z=X^2</math> הוא בעל התפלגות כי בריבוע עם דרגת חופש אחת.

ניסוי סטטיסטי הוא תהליך שבהתבסס על ערכים שנצפו במשתנה מקרי אחד או יותר, מאשש היפותזה סטטיסטית הנקראת [[השערת האפס]] (אותה מסמנים <math>\ H_0</math>) המייצגת טענה בנוגע להתפלגות המשתנה או המשתנים בהתאם ל[[מובהקות סטטיסטית|רמת מובהקות]] <math>\ \alpha</math>. רמת המובהקות מייצגת את ההסתברות שהשערת האפס תתקבל או תדחה (גם בניגוד לנכונותה). מצב שבו השערת האפס נדחית למרות היותה נכונה (כאשר ערך <math>\ \alpha</math> גבוה מדי) נקרא "[[טעות מסוג I]]". לעומתה, [[טעות מסוג II]] עלולה להתרחש כאשר רמת המובהקות נמוכה מדי, אז קיימת סכנה שהשערה תתקבל למרות היותה שגויה, דהיינו במקרה זה הרצף ייחשב כאקראי אף על פי שאינו כזה.

את הניסוי עורכים עם "נתון" סטטיסטי שהוא פונקציה של אלמנטים מהדגימה (כגון מספר האפסים או האחדים בדגימה). הנתון צריך להתאים להתפלגות הנורמלית או כי בריבוע של רצף אקראי אמיתי. את ערכי הנתון משווים עם ערכים ידועים מראש. לדוגמה אם <math>\ X</math> מתאים להתפלגות כי בריבוע עם <math>\ v</math> דרגות חופש וידוע שהנתון הסטטיסטי לצורך הניסוי אמור לקבל ערכים גבוהים יותר במקרה של אקראיות לקויה, קובעים ערך "סף" <math>\ x_\alpha</math> לפי נתון ידוע מראש (בדרך כלל בעקבות ניסויים בערכים אקראיים אמיתיים) ומחשבים את <math>\ \alpha=P(X_{\alpha})</math>, אם תוצאת הניסוי הנתון נמוכה מערך זה הרי שהרצף נכשל בבדיקה. בדרך דומה מחשבים את ערכי <math>\ \alpha</math> עבור כל ניסוי ספציפי ובודקים אם תוצאת הניסוי נמוכה מערך זה. אם בכל המקרים התוצאה גבוהה, אפשר לקבל את הרצף כאקראי. כמובן שיש להביא בחשבון אחוז נמוך של תוצאות, אפילו במקרה של רצף אקראי אמיתי שעלולות להיות נמוכות מערכי הסף שנקבעו, מה שמעיד כביכול על אקראיות לקויה. קביעת ערכי סף היא משימה קשה, ערכי סף בדרך כלל נקבעים אמפירית.

להלן מפורטים שישה מבחנים סטטיסטיים בסיסיים (המובאים בספר Handbook of Applied Cryptography).
במבחנים המתוארים <math>\ s=s_0,s_1,s_2,...,s_{n-1}</math> הוא סדרה של סיביות באורך <math>\ n</math>. כאשר <math>\ n</math> צריך להיות גדול, בין <math>\ 10^3</math> ל-<math>\ 10^6</math> (מיליון סיביות). רמת המובהקות נקבעה כאן <math>\ \alpha=0.05</math> (ערכים אחרים אפשריים אך דורשים התאמות בערכי הסף). דוגמה לטבלת ערכים באחוזים של התפלגות נורמלית כצפוי מהתנהגות משתנים אקראיים:

{| class="wikitable" border="1"
|-
| <math>\ \alpha</math> || 0.1 || 0.05 || 0.025 || 0.01 || 0.005 || 0.0025 || 0.001 || 0.0005
|- style="background-color: #EFEFEF;"
| <math>\ x</math> || 1.2816 || 1.6449 || 1.9600 || 2.3263 || 2.5758 || 2.8070 || 3.0902 || 3.2905
|}

למשל בכניסה <math>\ \alpha=0.05</math> והערך <math>\ x=1.6449</math>, משמעות הדבר שאם <math>\ X</math> בעל התפלגות נורמלית סטנדרטית אזי <math>\ X</math> חורג מהערך <math>\ 1.6449</math> בנקודה זו בחמישה אחוז מהמקרים בקירוב.

===מבחן תדירות (monobit test)===
בדיקה דו-כיוונית שמטרתה לוודא שמספר מופעי סיביות '1' ו-'0' זהה בקירוב, כצפוי מרצף אקראי. אם <math>\ n_0</math> ו-<math>\ n_1</math> מייצגים את סיביות '0' ו-'1' בהתאמה אזי הנוסחה היא:
:<math>\ \frac{(n_0-n_1)^2}{n}</math>

===מבחן סריאלי (two bit test)===
מטרת הבדיקה לקבוע האם מספר הזוגות 00, 01, 10, 11 המופיעים ברצף זהה בקירוב כצפוי מרצף אקראי. אם <math>\ n_{00}</math>, <math>\ n_{01}</math>, <math>\ n_{10}</math>, <math>\ n_{11}</math> מייצגים את הזוגות האמורים בהתאמה, אזי הנוסחה היא:
: <math>\ \frac{4}{n-1}(n^2_{00}+n^2_{01}+n^2_{10}+n^2_{11})-\frac{2}{n}(n^2_0+n^2_1)+1</math>

===מבחן פוקר (poker test)===
מחלקים את הרצף <math>\ s</math> ל-<math>\ k</math> חלקים כל אחד בגודל <math>\ \left \lfloor n/m \right \rfloor</math> סיביות כאשר <math>\ m</math> מקיים <math>\ \left \lfloor n/m \right \rfloor \ge 5\cdot (2^m)</math> והערך <math>\ n_i</math> מייצג את מספר המופעים של החלק ה-<math>\ i</math>. מבחן פוקר בודק האם מספר כל המופעים ברצף זהה בקירוב למספר הצפוי מרצף אקראי באמצעות הנוסחה:
:<math>\ \frac{2^m}{k}\left(\sum_{i=1}^{2^m}n^2_i\right)-k</math>
מבחן פוקר הוא הכללה של מבחן תדירות רק שכאן בודקים תדירות מופעים של תת-רצפים הגדולים מ-1.

===מבחן ריצות (runs test)===
מטרת הבדיקה לקבוע האם מספר הריצות (רצפים של סיביות אפס או אחד עוקבות) באורכים שונים, מופיעים ברצף בתדירות הצפויה מרצף אקראי. ריצה של אחדים נקראת כאן block ואילו ריצה של אפסים נקראת gap. מספר הריצות באורך <math>\ i</math> ברצף באורך <math>\ n</math> צריך להיות <math>\ (n-i+3)/2^i+2</math> אם <math>\ B_i</math> ו-<math>\ G_i</math> מייצגים את ריצות האפס והאחד בהתאמה, אזי נוסחת מבחן הריצה היא:
:<math>\ \sum_{i=1}^k\frac{(B_i-e_i)^2}{e_i}+\sum_{i=1}^k\frac{(G_i-e_i)^2}{e_i}</math>
כאשר <math>\ e_i=(n-i+3)/2^{i+2}</math>. ו-<math>\ k</math> מייצג את הריצה הארוכה ביותר כך שמתקיים <math>\ e_i \le 5</math>.

===מבחן אוטוקורלציה (auto-correlation)===
{{ערך מורחב|אוטוקורלציה}}
מטרת המבחן היא לחפש קורלציה (רמת מתאם) בין קטעים חופפים של הרצף. אם <math>\ d</math> הוא ערך הנמוך מ-<math>\left \lfloor n/2 \right \rfloor</math> מספר הסיביות ב-<math>\ s</math> שאינן מתאימות להזחה <math>\ d</math> הוא: <math>\ A(d)=\sum_{i=0}^{n-d-1}s_i\oplus s_{i+d}</math>. נוסחת האוטו-קורלציה היא:
: <math>\ 2\left(A(d)-\frac{n-d}{2}\right)/\sqrt{n-d}</math>

===מבחן אוניברסלי של מאורר===
יולי מאורר (Ueli M. Maurer) פרסם בירחון הקריפטוגרפיה (1992), מבחן אוניברסלי למחולל פסידו אקראי, שבניגוד למבחנים אחרים, מסוגל לאתר כל סוג של סטייה סטטיסטית משמעותית של פלט המחולל מפלט אקראי אמיתי. הרעיון מבוסס על העובדה שאם פלט המחולל ניתן ל[[דחיסת נתונים|דחיסה]] משמרת (ללא איבוד מידע) באופן משמעותי, הפלט אינו אקראי. במקום לנסות לדחוס את הפלט ממש, אלגוריתם מאורר מנסה להעריך את אורך הרצף הנבדק לאחר דחיסה. חסרונו העיקרי של האלגוריתם שנדרשת עבורו דגימה של פלט ארוך במידה רבה מהדרוש במבחנים המתוארים לעיל.

הרעיון של אלגוריתם מאורר הוא כדלהלן: מחלקים את הרצף s למקטעים לא חופפים כל אחד בגודל <math>\ L</math> סיביות (<math>\ L</math> הוא בטווח <math>\ [6,16]</math>), כאשר מספר הגושים הכולל צריך להיות <math>\ Q+K</math>. הערך <math>\ Q</math> צריך להיות לפחות <math>\ 10\cdot 2^L-1</math> ו-<math>\ K</math> צריך להיות לפחות <math>\ 1000\cdot2^L</math>. הערך <math>\ b_i</math> מייצג את המספר השלם שהייצוג הבינארי שלו הוא הגוש <math>\ i</math> בטווח <math>\ [1,Q+K]</math>. מייצרים טבלה <math>\ T</math> עם <math>\ Q+K</math> כניסות, ב-<math>\ Q</math> הכניסות הראשונות מציבים את מספר הגוש <math>\ b_i</math> האחרון שהופיע, כלומר עבור <math>\ i</math> מ-1 עד <math>\ Q</math> מציבים <math>\ T[b_i]=i</math> כאשר <math>\ i</math> מייצג את מספר הגוש <math>\ b_i</math> ברצף. <math>\ K</math> הכניסות הנותרות משמשות לחישוב הסטטיסטי כדלהלן. עבור כל גוש <math>\ i</math> מ-<math>\ Q+1</math> עד <math>\ Q+K</math> מציבים בכניסה <math>\ T[b_i]</math> את <math>\ i</math>. מסכמים את המרחקים עבור כל הגושים, כלומר את מספר הגושים מהמופע האחרון של הגוש ההאמור עד לגוש הנוכחי, מחשבים את ה[[לוגריתם]] בבסיס 2 של הסכום הסופי ומחלקים ב-<math>\ K</math>. כדלהלן:

: <math>\ \frac{1}{K}\sum_{i=Q+1}^{Q+K} \log_2(i-T[b_i])</math>
מאורר פרסם כמו כן טבלה של ערכי התוחלת <math>\ \mu</math> והשונות <math>\ \sigma^2</math> עבור הפרמטרים <math>\ L</math> השונים (בטווח שבין 6 ל-16) לצורך רמת מובהקות (<math>\ \alpha=0.01</math>) עבור המבחן האוניברסלי.

===תקן FIPS PB800-22 לבדיקת אקראיות===
המכון האמריקאי לסטנדרט וטכנולוגיה (NIST) פרסם במאי 2001 את PB800-22, חבילת תוכנה ותיעוד נלווה הכוללת מבחנים סטטיסטיים למחוללים אקראיים ופסידו אקראיים עבור אפליקציות קריפטוגרפיות. החבילה כוללת 16 מבחני אקראיות חזקים, המבוססים על מחקרים שנעשו בתחום עבור הממשל. כמו כן החבילה כוללת מספר ערכים קבועים לייחוס, המלצות ודוגמאות. להלן תקציר 16 המבחנים:

1. '''The Frequency (Monobit) Test'''
:מבחן תדירות הבודק אם מספר המופעים של '0' ו-'1' זהה בקירוב כצפוי מרצף אקראי. מבחן תדירות ידוע כמבחן החשוב ביותר ומומלץ לביצוע תחילה. אם הרצף הנבדק נכשל במבחן זה, מומלץ לעצור את הבדיקה ולהכריז על המחולל כלקוי, היות שרוב הסיכויים שהרצף לא יעבור את יתר המבחנים המנויים.

2. '''Frequency Test within a Block'''
:מבחן תדירות דומה למבחן הקודם מלבד זאת שהמבחן מתמקד במספר סיביות '1' בגושים בגודל <math>\ m</math> סיביות. ברצף אקראי אמיתי מספר סיביות '1' בממוצע בגוש נתון שואף ל-<math>\ m/2</math> (אם <math>\ m=1</math> מתקבל מבחן התדירות הראשון).

3. '''The Runs Test'''
: מבחן ריצות; מבחן דו כיווני הבודק אם מספר הריצות באורכים שונים ברצף הוא כצפוי מרצף אקראי. "ריצה" היא רצף של סיביות עוקבות זהות (0 או 1). המבחן בודק את מידת התנודתיות של הרצף, דהיינו המעבר מרצפים של אפס לרצפים של אחד וחוזר חלילה. מעבר מהיר מדי (הרבה ריצות קצרות) או אטי מדי (מעט ריצות ארוכות) מעיד על אקראיות לקויה.

4. '''Test for the Longest-Run-of-Ones in a Block'''
: מבחן ריצות ארוכות; מבחן הבודק אם הריצה הארוכה ביותר של אחדים (מזה משתמע גם אפסים) בגוש נתון אינו עולה על השיעור הצפוי מרצף אקראי.

5. '''The Binary Matrix Rank Test'''
:מבחן [[דרגה (אלגברה ליניארית)|דרגת]] מטריצה בינארית; מבחן הבודק את דרגות תת-מטריצות עוקבות של הרצף. המטרה היא לבדוק תלויות ליניאריות בתת-קטעים באורך קבוע מהרצף הנבדק ולהשוות את התוצאות מול תוצאות ידועות הצפויות מרצף אקראי.
[[קובץ:fourier transform.jpg|שמאל|ממוזער|250px|הדמיה של [[התמרת פורייה]] של רצף אקראי; בתרשים העליון לא נראית מחזוריות כלשהי, לעומתו בתרשים התחתון נראית בבירור מחזוריות המעידה על אקראיות לקויה]].

6. '''The Discrete Fourier Transform (Spectral) Test'''
:מבחן ספקטרלי ([[התמרת פורייה]]); מבחן הבודק מאפייני מחזוריות או דפוסיות ברצף הנבדק על ידי התמרת פורייה בדידה של הרצף. המבחן מתמקד במספר ה"פיקים" ותדירותם.

7. '''The Non-overlapping Template Matching Test'''
:מבחן התאמת תבניות לא חופפות; מבחן המתמקד בבדיקת תדירותן של תבניות קצרות קבועות מראש ברצף האקראי. "תבניות" הן רצפים בינאריים קצרים לא מחזוריים שנבחרו מראש. הסריקה מתבצעת באמצעות חלון בגודל <math>\ m</math> סיביות שתחילתו בסיבית הראשונה ברצף, אם לא נמצאה התאמה בין הסיביות שבחלון לבין תבנית נתונה, מתבצעת הזחה של החלון בסיבית אחת. אם נמצאה התאמה מתבצעת קפיצה של <math>\ m</math> סיביות ברצף וחוזר חלילה. מופעים רבים מדי של תבניות זהות מעידים על אקראיות לקויה.

8. '''The Overlapping Template Matching Test'''
:מבחן התאמת תבניות חופפות; בדומה למבחן הקודם, אך בשינוי קל. כאשר נמצאת התאמה בין התבנית לבין סיביות החלון מתבצעת הזחה של החלון רק בסיבית אחת. בכך מתאפשרת בדיקה גם של תבניות חופפות ברצף.

9. '''Maurer's "Universal Statistical" Test'''
:מבחן אוניברסלי של מאורר; אלגוריתם הבודק את מידת הדחיסות של הרצף הנקבעת לפי פרמטרים שחושבו מראש. מידת הדחיסות מאפשרת להעריך את מידת אקראיות הרצף. ככל שהרצף דחיס יותר כך אקראיותו נמוכה יותר.

10. '''The Lempel-Ziv Compression Test'''
:מבחן דחיסת [[אלגוריתם למפל-זיו|למפל-זיו]]; מבחן המנסה לבדוק את מידת אקראיות הרצף על ידי יישום וריאציה של אלגוריתם למפל זיו לדחיסת נתונים. בדומה למבחן הקודם ההנחה היא שככל שהרצף ניתן לדחיסה יותר כך אקראיותו נמוכה יותר. העיקרון הוא לבנות מילון של כל המילים (words) בכל האורכים (עד גבול מסוים) המופיעים ברצף. מספר המילים הסופי במילון משפיע על רמת האקראיות. מספר נמוך מעיד על אקראיות גרועה.

11. '''The Linear Complexity Test'''
:מבחן [[סיבוכיות ליניארית]]; מיושם באמצעות [[LFSR]]. כל רצף אקראי יכול להיות צירוף ליניארי כלשהו של רצף קצר יותר. למשל רצף באורך L סיביות יכול לשמש ליצירת רצף אקראי ארוך יותר על ידי חיבור בינארי או שילוב של חלק מהסיביות הקודמות והזזה צעד אחד לימין. [[אלגוריתם ברלקמפ-מסי]] מחשב סיבוכיות ליניארית של רצף סיביות על ידי מציאת [[אוגר הזזה|אוגר ההזזה]] הקטן ביותר האפשרי, אתו ניתן לשחזר את הרצף כולו. בעיקרון ככל שה-LFSR גדול יותר כך מידת האקראיות גבוהה יותר.

12. '''The Serial Test'''
:מבחן סריאלי; מבחן המתמקד בהסתברות מופעים של תבניות חופפות של m סיביות ברצף כולו. ברצף אקראי אחיד הסיכויים שרצף של <math>\ m</math> סיביות יופיע שווה לסיכויים של כל רצף אחר. כמובן שאם <math>\ m=1</math> מתקבל מבחן התדירות הראשון. ההבדל הוא שבמבחן זה בודקים תדירות של קטעים גדולים יותר מ-1 (כמו <math>\ m=3</math>). עבור רצף באורך <math>\ n</math> סיביות <math>\ m</math> צריך להיות נמוך מ-<math>\ \left \lfloor \log{n} \right \rfloor-2</math>.

13. '''The Approximate Entropy Test'''
:מבחן [[אנטרופיה (סטטיסטיקה)|אנתרופיה]] משוערת; בדומה למבחן הסריאלי במבחן זה בודקים תדירות מופעים של כל המחרוזות האפשריות באורך <math>\ m</math> סיביות לאורך כל הרצף אלא שכאן בודקים את תדירות גושים חופפים בגדלים סמוכים כמו <math>\ m</math> ו-<math>\ m+1</math> סיביות מול תוצאות ידועות שנצפו ברצפים אקראיים. בדרך זו נבדקת מידת הסדירות או אי-הסדירות של הרצף.

14. '''The Cumulative Sums (Cusums) Test'''
:מבחן סכום מצטבר; מבחן הבודק את אופי התנועה סביב האפס ב[[הילוך אקראי]] הנקרא גם "הילוך שיכור". ההילוך האקראי כאן מתבצע על ידי חישוב הסכום המצטבר של סיביות הרצף כשהם מוחלפות ב-<math>\ 1</math> ו-<math>\ (-1)</math> בהתאמה. הגרף הנוצר מהילוך אקראי ברצף אקראי אמיתי, מראה שקיימת תנודתיות מסוימת סביב ציר האפס. בדיקה והשוואה של התנודתיות של הרצף הנבדק מעידה על טיב אקראיותו. תנועה הדוקה מדי או מופרעת מדי מעידה על אקראיות לקויה.

15. '''The Random Excursions Test'''
:מבחן הילוך אקראי; בדומה לבדיקה הקודמת, כאן מתמקדים במספר המעגלים או ביקורים בנקודה מסוימת בסכום המצטבר של הילוך האקראי. "מעגל" של הילוך אקראי הוא סדרת צעדים אקראיים ביחידות מרחק מוגדרות שחוזרת לאחר מספר מסוים של צעדים לנקודת המוצא. הרעיון של המבחן הוא לבדוק אם מספר הביקורים (מעגלים) בנקודות מוצא שונות הוא בתדירות הצפויה מרצף אקראי. המבחן מורכב למעשה מאיסוף מידע על 8 נקודות מוצא 4 מהם מעל האפס והיתר מתחת לאפס.

16. '''The Random Excursions Variant Test'''
:מבחן הילוך אקראי (גרסה שונה); בהתבסס על המבחן הקודם, בגרסה זו בודקים את מספר הביקורים הכולל בנקודת מוצא נתונה בסכום המצטבר של ההילוך האקראי. המבחן למעשה מורכב מ-18 מצבים (נקודות מוצא) שונים.

==אקראיות סטטיסטית והתפלגות סטטיסטית==
כאשר עולה צורך במספרים אקראיים בעלי ב[[התפלגות נורמלית]], אפשר להשתמש במספרים אקראיים בעלי [[התפלגות אחידה רציפה|התפלגות אחידה]] בטווח שבין אפס לאחד כדי לייצר מספרים בכל התפלגות רצויה על ידי העברתם בפונקציה הופכית של [[פונקציית התפלגות מצטברת]], עם ההתפלגות הדרושה. כדי לייצר זוג מספרים אקראיים <math>\ (x,y)</math> בלתי תלויים בעלי התפלגות נורמלית, אפשר לייצר תחילה [[קואורדינטות קוטביות]] <math>\ (r, \theta)</math> כאשר <math>\ r~X^2_2</math> ו-<math>\ \theta</math> ערך בהתפלגות אחידה בטווח <math>\ (0, 2\pi)</math>. ראו טרנספורמציית [[Box-Muller]].

אפשר לייצר מספרים אקראיים גם באמצעות פונקציות התפלגות סטטיסטית כמו [[פונקציית הצטברות]] או [[פונקציית צפיפות]] של [[משתנה מקרי]] נורמלי. שיטה אחת היא שיטת ההיפוך האינטגרלית אתה משתמשים לייצר ערכי מדגם אקראיים מתוך כל התפלגות נתונה בהינתן פונקציית ההתפלגות המצטברת, בשיטה זו מחשבים את האינטגרל של שטח מסוים השווה או נמוך ממספר שנבחר באקראי מהטווח (0,1). שיטה אחרת נקראת "שיטת דחייה-קבלה", המשמשת גם היא ליצירת ערכים מדגמיים אקראיים מהתפלגות נתונה. בוחרים זוג ערכים x,y ובודקים אם הפונקציה של x גדולה או שווה לערך y. אם כן ערכו של x "מתקבל" אחרת ערכו "נדחה" וחוזר חלילה.

==ראו גם==
*[[משתנה מקרי]]
*[[התפלגות]]

== קישורים חיצוניים ==
{{ויקישיתוף בשורה}}
* [http://www.cacr.math.uwaterloo.ca/hac Handbook of Applied Cryptography] פרק 5.
* [http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22b.pdf SP800-22b A Statistical Test Suite for Random And Pseudorandom Number Generators For Cryptographic Applications]
* [http://citeseer.ist.psu.edu/maurer92universal.html Ueli M. Maurer, A Universal Statistical Test for Random Bit Generators, Journal of Cryptology, vol. 5, no. 2, 1992, pp. 89-105]

[[קטגוריה:יצירת מספרים אקראיים]]

[[de:Zufallszahlengenerator#Physikalischer Zufallszahlengenerator]]