מספרים אקראיים

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

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

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

תוכן עניינים

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

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

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

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

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

[עריכה] מבחנים סטטיסטיים

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

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

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

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

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

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

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


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

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

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

[עריכה] מחוללים פסאודו-אקראיים

אחת השיטות להפקת מספרים פסאודו אקראיים היא באמצעות פונקציה חד-כיוונית. הדוגמא הנפוצה למחולל כזה נקראת 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" (כרך שני). קאנות' צוטט פעם כאומר: "זהו חטא לחשוב כי ניתן לייצר מספרים אקראיים בשיטות מתמטיות".

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

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

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

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

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

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

מספרים אקראיים הינם מרכיב חשוב במנגנוני הצפנה רבים. מפתחות הצפנה מיוצרים באופן אקראי על מנת להקשות על ניחושם. פרוטוקולים ומנגנונים קריפטוגרפיים רבים משתשמים במספרים אקראיים למטרות שונות. מרבית האלגוריתמים הקיימים בשוק אינם עומדים בדרישות בטיחות מינימליות ואינם בטוחים מבחינה קריפטוגרפית כלל. אלגוריתם פסאודו-אקראי קריפטוגרפי מיושם בדרך כלל באמצעות אלגוריתם הצפנה בטוח. מאחר ואלגוריתמים להצפנה מכילים מטבעם את התכונה שהם קשים לניחוש, הם מהווים מקור מצויין לאקראיות. ישנם מספר שיטות להפקת רצף פסאודו-אקראי המתאים למטרות קריפטוגרפיות. בשיטות סימטריות משתמשים באלגוריתם סימטרי מהיר כגון 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.

[עריכה] קישורים חיצוניים

[עריכה] ראו גם