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

מחולל מספרים פְּסֵידוֹ-אקראיים (בקיצור PRNG), הוא אלגוריתם במחשב המייצר סדרת מספרים או אלמנטים המדמים בקירוב תכונות של רצף אקראי שנוצר באמצעות מחולל מספרים אקראיים אמיתי. לאמיתו של דבר, רצף פסידו-אקראי אינו אקראי היות שהוא נוצר בשיטה דטרמיניסטית מתוך קבוצה קטנה יחסית של אלמנטים הנקראת גרעין (seed) או מצב התחלתי (initial state) ובהינתן מידע זה ניתן לשחזור מדויק, מסיבה זו מכונה "פסידו" דהיינו "מדומה". באמצעות אלגוריתמים המיוחדים לכך, ניתן לייצר רצפים פסידו אקראיים, הקרובים מאוד באיכותם לרצפים שנוצרו באמצעות מחולל אמיתי, באופן שקשה מאוד מבחינה סטטיסטית חישובית להבדיל ביניהם. מחוללים פסידו אקראיים משחקים תפקיד חשוב בסימולציה לצורך מדעי, הימורים, משחקי מחשב וקריפטוגרפיה.
בין משפחות האלגוריתמים הנפוצים כיום נמנים גרסאות של Linear Congruential Generators בקיצור LCG המחולל הנפוץ ביותר המבוסס על אריתמטיקה מודולרית. משפחת מחוללי Lagged Fibonacci generator בקיצור LFG המבוסס על סדרת פיבונאצ'י וכן Linear Feedback Shift Generator בקיצור LFS שהוא אוגר הזזה-החזרה המיושם בחומרה בדרך כלל ונפוץ בגרסאות מסוימות של צופני זרם. כמו כן קיימים מחוללים אקראיים חדשים כמו Blum Blum Shub (בקיצור BBS) המבוסס על אריתמטיקה מודולרית וכן Fortuna, Mersene Twister ו-Multiply-with-carry של ג'ורג' מרסגליה הידוע גם בשל פיתוח סוללת Diehard (שמרן) - אוסף של מבחנים סטטיסטיים שונים לבדיקת אקראיות.
אלגוריתם פסידו אקראי מקבל כקלט קבוצה קטנה של מספרים אקראיים הנקראת גרעין התחלתי ומפיק פלט של סדרת מספרים פסידו אקראיים בהתפלגות אחידה באורך הרצוי. תפקיד המחולל הוא למעשה "למתוח" את הקלט לאורך הרצוי תוך שמירה על רמת אקראיותו במידת האפשר. הגרעין ההתחלתי צריך להיות ממקור אקראי ולא ערך קבוע, שאם לא כן תוצאת המחולל תחזור על עצמה בדיוק. מקור אקראי יכול להיות כל אמצעי פיזי בדוק שניתן להפיק ממנו מספרים אקראיים כמו מחולל אקראי או בדרך קלה יותר, ניצול אנטרופיה זולה הזמינה בכל מערכת הפעלה כגון: מספר מילי שניות שחלפו מאז הפעלת המחשב, נתוני ניהול זיכרון, אפיקי קלט/פלט, יומני תיעוד, הקשות מקלדת, קואורדינטות העכבר או כל אירוע אקראי אחר. לחיזוק האקראיות לעיתים מעבירים את הפלט הפונקציה בפונקציית גיבוב או פונקציות הצפנה. 
את הפלט האקראי יש לבדוק בזהירות באמצעות מבחנים סטטיסטיים ידועים, בהתאם לרמת האקראיות הנדרשת. רוברט קוביו פרסם פעם מאמר שכותרתו "יצירת מספרים אקראיים חשובה מדי מכדי להותירה בידי הגורל". וכמו שהתבדח פעם ג'ון פון נוימן: "עצם המחשבה להשתמש בשיטות אריתמטיות ליצירת מספרים אקראיים היא בגדר חטא". דונלד קנות' כתב בספרו (The Art of Computer Programming) "אין לייצר מספרים אקראיים באמצעות אלגוריתם שנבחר באקראי".

מחזוריות

אם הגרעין התחלתי קבוע, המחולל ייצר רצף זהה שוב ושוב. היות שהרצף מיוצר מתוך קבוצה מוגבלת של מספרים, בסופו של דבר יחזור על עצמו, דהיינו בשלב כלשהו סדרת המספרים שהמחולל מייצר תחזור שוב לנקודת ההתחלה. תופעה זו תתרחש במעגל אין סופי. האורך המקסימלי של הרצף לפני שהוא מתחיל לחזור על עצמו נקרא "מחזור" (period). אורך המחזור אותו מודדים בסיביות, נקבע על ידי מספר פרמטרים, בראשם המצב התחלתי. בבחירה מושכלת של פרמטרים, אפשר לייצר רצף אקראי סביר לכל צורך מעשי ובכל אורך רצוי. הוכח כי אם המצב ההתחלתי של המחולל מכיל  סיביות אזי המחזור המרבי לא יעלה על  סיביות. באמצעות אלגוריתמים מסוימים אפשר לחשב מחזוריות מחולל אקראי מבלי לעבור על פני כל המספרים במחזור. LFSR בדרך כלל מתוכנן לייצר רצף אקראי מקסימלי, באורך של  סיביות בדיוק.  שילוב של שיטות שונות מניב בדרך כלל מחזוריות מסדר הגודל של  (ראו פרדוקס יום ההולדת ושיטת רו של פולארד).
מהיבט של תורת האינפורמציה קיימת שאלה פתוחה מבחינה תאורטית ומעשית, האם ניתן לייצר רצף פסידו אקראי מתוך גרעין התחלתי אקראי אמיתי, באיכות כזו שלא ניתן להבחין בינו ובין רצף אקראי שנוצר על ידי מחולל אמיתי תוך שימוש בעצמת חישוב מוגבלת, אם לא ידוע הגרעין ההתחלתי והאלגוריתם ששימש ליצירת המספרים. כמעט כל מערכת קריפטוגרפית כוללת שימוש בדרך זו או אחרת במחולל פסידו אקראי. בטיחות מרבית האלגוריתמים והפרוטוקולים הקריפטוגרפיים נשענת על ההנחה שלא ניתן מעשית להבחין בין תוצאה של מחולל פסידו אקראי ומחולל אקראי אמיתי. הדוגמה המתבקשת היא צופן זרם, צופן זרם ביסודו כולל מחולל פסידו אקראי מובנה המייצר סדרת מספרים אקראיים המהווים מפתח הצפנה אותו מחברים ב-XOR עם המסר הקריא ליצירת טקסט מוצפן.
פיתוח מחולל פסידו אקראי המתאים ליישום קריפטוגרפי הוא משימה קשה. מבחינה מעשית, פלט מחוללים פסידו אקראיים נפוצים סובל מפגמים רבים שמתגלים במבחנים סטטיסטיים. ביניהם מחזוריות קצרה מן הצפוי של מצב התחלתי מסוים או קורלציה. מצב התחלתי הגורם למחזוריות הרצף להיות קצרה מהצפוי נקרא 'חלש' במובן שבהינתן מצב התחלתי הזה פלט המחולל אינו בעל התפלגות אחידה ועל כן אקראיותו לקויה. לעיתים עולה במבחנים סטטיסטיים שהמחולל אינו מפיק פלט הדומה בתכונותיו לפלט אקראי אמיתי. לדוגמה אלגוריתם RANDU, שזכה לתפוצה רחבה בעיקר בשנות השישים של המאה ה–20, במערכות הפעלה של מחשבים מרכזיים. האלגוריתם יישם את רעיון מחולל LCG עם פרמטרים שנבחרו באופן לקוי, עקב כך מעריכים שנגרם לא אחת נזק למחקרים שהסתמכו על המחולל.

היסטוריה

אחת השיטות המוקדמות ליצירת מספרים פסידו אקראיים באמצעות מחשב, הייתה של ג'ון פון נוימן ב-1946. השיטה הייתה מאוד פשוטה והיא נקראה "אמצע הריבוע", כדלהלן; מעלים מספר כלשהו בריבוע ונוטלים חלק מספרותיו האמצעיות כחלק מרצף אקראי, איתו משתמשים לאחר מכן כגרעין לחישוב הבא וחוזר חלילה. לדוגמה אם מעלים בריבוע את המספר 1111 מתקבל 1234321 אם מוסיפים אפס בהתחלה אפשר לשלוף את ארבע הספרות האמצעיות "2343" כמספר אקראי. אם מעלים את 2343 בריבוע, מוסיפים אפס מתקבל מספר שארבע ספרותיו האמצעיות הם 4896 וכן הלאה. פון ניומן השתמש במספר בן 10 ספרות. 
הבעיה עם שיטה זו היא שמספרים התחלתיים מסוימים נוטים להפיק מחזוריות קצרה מדי. פון ניומן היה מודע לכך אולם הסתפק בשיטה זו לצרכיו. הוא היה מודאג יותר בשל החשש שתיקונים מתמטיים כלשהם עלולים יותר להסתיר את הבעיה מאשר לתקנה. פון ניומן נמנע משימוש במחולל מבוסס חומרה בשל העובדה שכדי לבדוק אקראיות היה צורך באחסון מספרים רבים בזיכרון והמחשבים שהוא השתמש בהם אז כמו ENIVAC היו מוגבלים מאוד בזיכרון מה שהיה עלול לגרום להאטה חמורה בביצועים. השיטה שאימץ למרות היותה לקויה היוותה מעין פשרה סבירה. כמובן שכיום השיטות הידועות ליצירת מספרים אקראיים מהירות ויעילות מהשיטה של פון ניומן.

Linear congruential generator

שיטת Linear congruential היא השיטה הוותיקה והפופולרית ביותר כיום. היא הוצעה לראשונה על ידי דריק הנרי להמר ב-1949. הרעיון מאחורי משפחה זו של אלגוריתמים (הנקראת בקיצור LCG) פשוט בתכלית ובדרך כלל קל ליישום. המחולל מוגדר על ידי נוסחת הנסיגה:  כאשר  הוא האיבר ה- בסדרת המספרים הפסידו-אקראית המופקת. הפרמטר  מכונה מודולוס,  נקרא "כופל" ו- נקרא "מקדם" (במקרה של  מתקבל אלגוריתם פארק-מילר שנמצא בשימוש נרחב, בין היתר, במערכות ההפעלה של מקינטוש).  נקרא "מצב התחלתי" או גרעין התחלתי ובדרך כלל צריך להיות ממקור אקראי כלשהו. השפעת הפרמטרים  על פלט המחולל מכרעת.
LCG אינו מתאים לצורך קריפטוגרפי,מחקרים מראים שניתן לנחש את המשך הרצף מתוך קטע קצר יחסית גם ללא ידיעת הפרמטרים. הסוגים השונים של משפחה זו נבדלים בעיקר בערכי הפרמטרים. מחזוריות המחולל תלויה בראש ובראשונה בפרמטר . למשל גרסת המחולל של פארק-מילר עם המודולוס  (שהוא מספר מרסן ראשוני) והפרמטרים ,  מגיעה למחזוריות בסדר גודל של .
להלן קוד C++ של המחולל הפסידו אקראי המובנה בסביבת הפיתוח של מיקרוסופט ויז'ואל סטודיו, המבוסס על LCG עם הפרמטרים :
return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
הערך 0x7FFF משמש לצמצום מודולרי. המחולל מפיק מספר פסידו אקראי בגודל 15 סיביות.

Lagged Fibonacci generator

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

Mersenne twister

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

מחולל אקראי בעל התפלגות נורמלית

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