מספר אקראי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

מספר אקראי אמיתי[עריכת קוד מקור | עריכה]

לא ניתן לקרוא למספר "אקראי" ללא הקשר כלשהו. לדוגמה: אם נתונים במכל 49 כדורים זהים הממוספרים מ-1 עד 49 ואם שולפים מתוך המכל (לאחר ערבוב הגון) כדור אחד ועליו מופיע המספר 23 ניתן לומר כי המספר 23 הוגרל באופן אקראי בהתפלגות אחידה מתוך הקבוצה \ \{1,2,...,49\}. ההסתברות שהמספר 23 יוגרל היא \ 1/49. אם נרשום את המספר המופיע על הכדור, נחזירו למכל ונחזור על תהליך זה מספר פעמים, נקבל רצף אקראי המוגדר מעל הקבוצה \ \{1,2,...,49\}. לדוגמה: הסיכוי שיוגרל הרצף: \ 17,45,1,7,23,35 (בהנחה שכל כדור מוצא, נרשם ומוחזר שוב) היא \ (1/49)^6 או \ 49^{-6} שהיא כפולה של ההסתברויות של כל כדורים ברצף.

מחוללים אקראיים[עריכת קוד מקור | עריכה]

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

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

מבחנים סטטיסטיים[עריכת קוד מקור | עריכה]

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

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

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

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

מספר פסבדו אקראי[עריכת קוד מקור | עריכה]

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

תוצאת מחולל סיביות פסבדו-אקראי (PRBG) אינה אקראית לגמרי. למעשה עבור גרעין התחלתי באורך \ k, מספר הרצפים שהמחולל מסוגל לייצר באורך \ l מהווה רק חלק קטן מהטווח המקסימלי ליתר דיוק \ 2^k/2^l של כל הרצפים הבינאריים האפשריים באורך \ l. השאיפה היא למצוא שיטה להרחבת גרעין התחלתי קצר לרצף באורך מרבי, באופן שלא ניתן יהיה להבחין בינו לבין רצף באורך זהה המיוצר בעזרת מחולל אמיתי. קיים מגוון עצום של אלגוריתמים ליצירת מספרים פסבדו-אקראיים מסוגים שונים. אולם רבים מהם אינם בטוחים ויש להיזהר בטענת הממציאים באשר לטיב אקראיותם.

אלגוריתמים אקראיים[עריכת קוד מקור | עריכה]

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

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

מחולל פסבדו אקראי (PRNG)[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – מחולל פסבדו אקראי

אחת השיטות להפקת מספרים פסבדו-אקראי היא באמצעות פונקציה חד-כיוונית. הדוגמה הנפוצה למחולל כזה נקראת Linear congruential generator או בקיצור LCG שהומצאה על ידי Lehmer והפכה לתקן ANSI שיושם בעבר בפונקציה \ \mbox{rand()} בשפת c. הרעיון הבסיסי של המחולל פשוט ויעיל ומתבסס על אריתמטיקה מודולרית, משוואתו היא: \ x_n = (ax_{n-1} + b) \mbox{ mod }m, כאשר \ n גדול מאפס וערכו של \ x_0 הנו הגרעין ההתחלתי. הפרמטרים \ a,b,m שולטים באופי התוצאה. בשל השימוש במודולו המחולל מייצר רצף סיביות סופי, כלומר מחזורי. כאשר לאחר מספר מסוים של אלמנטים המחולל חוזר על עצמו. מחזוריות המחולל היא על כן עניין קריטי, בחירת הפרמטרים עבור המחולל חשובה ולמעשה משפיעה ישירות על מחזוריותו. למשל אם \ m=2^{31}, a=1103515245, b=12345 אזי מחזוריות המחולל תהיה בערך \ 2^{30}. ישנן גרסאות משופרות ממשפחת אלגוריתמים אלו כמו אלגוריתם Park-Miller.

למרות שאלגוריתם זה עומד יפה במבחנים סטטיסטיים ידועים לבדיקת אקראיות וגרסאות שונות שלו נפוצות מאוד בשימוש מעשי, הוא אינו בטוח כלל מבחינה קריפטוגרפית. מאחר שהמשכו ניתן לניחוש מתוך רצף קצר יחסית. ג'ואן בויר, קראווציק ואחרים הראו כיצד ניתן לנחש את תוצאות מחולל מסוג זה מתוך רצף קצר (ללא ידיעת הגרעין ההתחלתי), בידיעת חלק מן הפרמטרים ואף בלא ידיעת הפרמטרים כלל. התיעוד המקיף ביותר בנושא זה הוא ספרו של דונלד קאנות' "The art of computer programming" (כרך שני). ג'ון פון נוימן צוטט כאומר: "זהו חטא לחשוב כי ניתן לייצר מספרים אקראיים בשיטות מתמטיות".

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

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

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

  • שעון מערכת.
  • הפרשי זמן בין הקשות מקלדת או קואורדינטות העכבר.
  • תכולת אפיק קלט/פלט של המחשב.
  • קלט משתמש.
  • נתוני מערכת ההפעלה או תיעוד ביצועי רשת.

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

אלגוריתם פסבדו אקראי קריפטוגרפי[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – מחולל פסבדו אקראי קריפטוגרפי

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

אלגוריתם BBS הוא דוגמה טובה למחולל בינארי אקראי-קריפטוגרפי המבוסס על הצפנה אסימטרית. המחולל פועל לפי הנוסחה: \ x_i=x^2_{i-1}\mbox{ mod }n. בכל שלב הסיבית הנמוכה של \ x_i מהווה חלק מהרצף האקראי, כאשר \ n הנו כפולה של שני מספרים ראשוניים גדולים. ניסיון לנחש את הסיבית הבאה של המחולל שקול לניסיון לפרק את \ n לגורמים. אם הגורמים הראשוניים של \ n אינם ידועים, המחולל יהיה בטוח. מאחר שבטיחות המחולל תלויה בקושי שבפירוק \ n לגורמים, רצוי ש-\ n יהיה גדול ככל האפשר. החיסרון היחידי של האלגוריתם הוא שכל סיבית אקראית דורשת העלאה בריבוע מודולו \ n, פעולה יקרה במונחי חישוב. ניתן לשפר את האלגוריתם בכך שפלט האלגוריתם בכל לולאה יהיה מספר מסוים של הסיביות הנמוכות של \ x_i.

לקריאה נוספת[עריכת קוד מקור | עריכה]

דונלד קאנות', The art of computer programming, Vol 2: Seminumerical Algorithms.

קישורים חיצוניים[עריכת קוד מקור | עריכה]