מחולל מספרים אקראיים

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

שיטות פיזיקליות (חומרה)

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

יישומים מעשיים

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

הלבנה (whitening)

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

אקראיות סטטיסטית והתפלגות סטטיסטית

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