מספר אקראי

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

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

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

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

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

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

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

מספר אקראי הוא מספר שנבחר בלי לסדר מראש. לפעמים בוחרים מתוך קבוצה שבה לכל מספר יש אותו סיכוי.

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

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

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

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