אלגוריתמים אקראיים עושים שימוש במספרים אקראיים. בזמן ריצה מבצע האלגוריתם החלטות בהתאם לערך אקראי כלשהו. בשל כך ייתכן מצב שבו האלגוריתם יחזיר תשובה שונה עבור קלט זהה. מסיבה זו נקראים אלגוריתמים אלו "אקראיים", בניגוד לאלגוריתמים דטרמיניסטיים, שעבור קלט זהה יבצעו תמיד אותן החלטות ותוצאתם תהיה תמיד זהה. דוגמה לשימוש במספרים אקראיים היא אלגוריתם מילר-רבין לבדיקת ראשוניות, שבמימושו הבסיסי נעשה שימוש במספרים אקראיים. אלגוריתם זה הוא אלגוריתם הסתברותי, כיוון שאינו מחזיר תשובה שנכונותה ודאית. השימוש באקראיות כשיטה לבדיקת ראשוניות יעיל יותר מאלגוריתמים דטרמיניסטיים מקבילים.
דוגמה נוספת לשימוש במספרים פסאודו-אקראיים היא שיטת מונטה קרלו, המשתמשת במספרים אקראיים לפתרון בעיות חישוביות.
מחולל פסאודואקראי (PRNG).
אחת השיטות להפקת מספרים פסאודו-אקראי היא באמצעות פונקציה חד-כיוונית. הדוגמה הנפוצה למחולל כזה נקראת Linear congruential generator או בקיצור LCG שהומצאה על ידי Lehmer והפכה לתקן ANSI שיושם בעבר בפונקציה formula_11 בשפת c. הרעיון הבסיסי של המחולל פשוט ויעיל ומתבסס על אריתמטיקה מודולרית, משוואתו היא: formula_12, כאשר formula_13 גדול מאפס וערכו של formula_14 הוא הגרעין ההתחלתי. הפרמטרים formula_15 שולטים באופי התוצאה. בשל השימוש במודולו המחולל מייצר רצף סיביות סופי, כלומר מחזורי. כאשר לאחר מספר מסוים של אלמנטים המחולל חוזר על עצמו. מחזוריות המחולל היא על כן עניין קריטי, בחירת הפרמטרים עבור המחולל חשובה ולמעשה משפיעה ישירות על מחזוריותו. למשל אם formula_16 אזי מחזוריות המחולל תהיה בערך formula_17. ישנן גרסאות משופרות ממשפחת אלגוריתמים אלו כמו אלגוריתם Park-Miller.
אף על פי שאלגוריתם זה עומד יפה במבחנים סטטיסטיים ידועים לבדיקת אקראיות וגרסאות שונות שלו נפוצות מאוד בשימוש מעשי, הוא אינו בטוח כלל מבחינה קריפטוגרפית. מאחר שהמשכו ניתן לניחוש מתוך רצף קצר יחסית. ג'ואן בויר, קראווציק ואחרים הראו כיצד ניתן לנחש את תוצאות מחולל מסוג זה מתוך רצף קצר (ללא ידיעת הגרעין ההתחלתי), בידיעת חלק מן הפרמטרים ואף בלא ידיעת הפרמטרים כלל. התיעוד המקיף ביותר בנושא זה הוא ספרו של דונלד קנות' "The art of computer programming" (כרך שני). ג'ון פון נוימן צוטט כאומר: "זהו חטא לחשוב כי ניתן לייצר מספרים אקראיים בשיטות מתמטיות".
איכות המחולל תלויה ביישום, בדרישות ובמטרה לשמה הוא משמש. משחקי מחשב למשל דורשים אקראיות נמוכה ביותר, עבורם מחוללים המובנים במהדר נפוץ מספקים. לעומתם משחקי הימורים דורשים אלגוריתמים טובים ומורכבים יותר. יישומים קריפטוגרפיים דורשים אקראיות מרבית. להלן הדרישות מכל מחולל פסאודו-אקראי (בסדר עולה של חשיבותן), כדי שיהיה בטוח:
שתי האחרונות נדרשות בעיקר ביישומים קריפטוגרפיים, למשל לצורך הכנת מפתחות הצפנה. כאמור, בחירת גרעין התחלתי אקראי (אמיתי) הכרחית. קיימים מספר מקורות אקראיים טובים להפקת גרעין התחלתי קצר, כגון:
לעיתים משלבים מספר מקורות אקראיים באמצעות פונקציית ערבול בטוחה, להשגת אקראיות מרבית.
אלגוריתם פסאודודו אקראי קריפטוגרפי.
מספרים אקראיים הם מרכיב חיוני במנגנוני הצפנה רבים. מפתחות הצפנה מיוצרים באופן אקראי כדי להקשות על ניחושם. פרוטוקולים ומנגנונים קריפטוגרפיים רבים משתמשים במספרים אקראיים למטרות שונות. מרבית האלגוריתמים הקיימים בשוק אינם עומדים בדרישות בטיחות מינימליות ואינם בטוחים מבחינה קריפטוגרפית כלל. אלגוריתם פסאודו-אקראי קריפטוגרפי מיושם בדרך כלל באמצעות אלגוריתם הצפנה בטוח. מאחר שאלגוריתמים להצפנה מכילים מטבעם את התכונה שהם קשים לניחוש, הם מהווים מקור מצוין לאקראיות. ישנן מספר שיטות להפקת רצף פסאודו-אקראי המתאים למטרות קריפטוגרפיות. בשיטות סימטריות משתמשים באלגוריתם סימטרי מהיר כגון AES בתור מחולל אקראי. בשיטה זו מצפינים ערך קבוע כלשהו (בדרך כלל אפסים), כאשר מפתח ההצפנה הוא הגרעין ההתחלתי. פלט הצופן מהווה חלק מהרצף האקראי. בשיטות א-סימטריות מפיקים רצף אקראי באמצעות נוסחאות הדומות לאלגוריתמים כגון RSA והצפנת רבין.
אלגוריתם BBS הוא דוגמה טובה למחולל בינארי אקראי-קריפטוגרפי המבוסס על הצפנה אסימטרית. המחולל פועל לפי הנוסחה: formula_18. בכל שלב הסיבית הנמוכה של formula_19 מהווה חלק מהרצף האקראי, כאשר formula_13 הוא כפולה של שני מספרים ראשוניים גדולים. ניסיון לנחש את הסיבית הבאה של המחולל שקול לניסיון לפרק את formula_13 לגורמים. אם הגורמים הראשוניים של formula_13 אינם ידועים, המחולל יהיה בטוח. מאחר שבטיחות המחולל תלויה בקושי שבפירוק formula_13 לגורמים, רצוי ש-formula_13 יהיה גדול ככל האפשר. החיסרון היחידי של האלגוריתם הוא שכל סיבית אקראית דורשת העלאה בריבוע מודולו formula_13, פעולה יקרה במונחי חישוב. ניתן לשפר את האלגוריתם בכך שפלט האלגוריתם בכל לולאה יהיה מספר מסוים של הסיביות הנמוכות של formula_19.
לקריאה נוספת.
דונלד קנות', The art of computer programming, Vol 2: Seminumerical Algorithms.
לובלין
לוּבְּלִין (בפולנית: Lublin, ; בליטאית: Liublinas; באוקראינית: Люблін) היא עיר במזרח פולין ומושב הגמון. בעיר התגוררו בשנת 2008 כ-350,462 תושבים. העיר הייתה מושב של כמה פרלמנטים פולניים וגם מושב בית הדין העליון של פולין. בשנת 1569 נחתם בעיר הסכם לובלין - האיחוד בין פולין ובין ליטא.
לובלין והיהודים.
תחילת ההתיישבות היהודית בלובלין הייתה ככל הנראה ב-1456, אך רק בשנת 1500 הורשו יהודים לגור בתוך העיר עצמה (עד אז גרו בפרברי העיר). שלושים ושלוש שנים אחרי ההיתר לגור בתוך העיר הוקם בעיר בית דין יהודי ראשון.
יהודי לובלין התפזרו במשך השנים ברחבי מזרח פולין, למחוז זמושץ' ולעיירות כמו טומשוב לובלסקי.
ללובלין נודעה חשיבות רבה בהיסטוריה היהודית, והיו בה מוסדות יהדות גדולים כמו ישיבת חכמי לובלין. לפני השואה היו בה 122 אלף תושבים, 40 אלף מתוכם יהודים. בין הרבנים בעיר במשך השנים: רבי יעקב פולק, רבי שלום שכנא מלובלין, מהרש"ל, רבי שמעון וולף אוירבך, רבי מרדכי יפה, מהרש"א, מהר"ם מלובלין, החוזה מלובלין, רבי עזריאל הורוביץ ("ראש הברזל"), רבי משולם זלמן אשכנזי, רבי דב בריש אשכנזי רבי צדוק הכהן מלובלין, רבי יהודה לייב איגר, רבי שניאור זלמן פרדקין "הגאון מלובלין", רבי אליהו קלצקין, רבי יהודה מאיר שפירא, שייסד בה את ישיבת חכמי לובלין, ועוד.
ב-18 בספטמבר 1939, נכבשה לובלין על ידי גרמניה. כחלק מהפתרון הסופי ניסתה ההנהגה הנאצית להפוך את לובלין למעין מקום ריכוז של היהודים (תוכנית לובלין). הניסיון החל עם כניסת הגרמנים לעיר אך נכשל, וב-1940 נזנח כליל. גורל יהודי לובלין לא היה שונה מגורל יהודי מקומות אחרים באירופה.
הנאצים הקימו באזור לובלין מספר מחנות השמדה ומחנות ריכוז, ביניהם: בלז'ץ, מיידאנק וסוביבור.
כרבע מתושבי קהילת לובלין גורשו מן העיר על ידי הנאצים לעיירות בסביבה. יהודי העיר שנותרו בה וכן פליטים ומגורשים ממקומות שונים בפולין, כ-34,000 במספר, נכלאו בגטו לובלין, שהוקם בעיר באביב 1941.
קרוב ל-29,000 מיהודי הגטו נשלחו אל מותם במחנה ההשמדה בלז'ץ בגירוש ההמונים הגדול שהיה בחודשים מרץ-אפריל 1942, והיו מקורבנותיו הראשונים של מחנה השמדה זה. מאות יהודים אחרים נורו למוות בחורשות שבפאתי העיר.
אלפים בודדים שנותרו בגטו לאחר הגירוש שוכנו בגטו קטן שהוקם בפרבר "מיידן טטרסקי" בתנאים קשים ומרביתם נשלחו במספר גירושים למחנה ההשמדה מיידאנק שהוקם בסמיכות לעיר במהלך שנת 1942.
אחרוני היהודים שנותרו בעיר והועסקו במלאכות שונות עבור הנאצים, חוסלו במאי 1943.
עד היום משמש אתר מחנה ההשמדה מיידאנק, שהנאצים לא סיימו את פירוקו, כאתר הנצחה וכעדות לפשעי הנאצים.
פרק מדמותה היהודית של לובלין בסוף המאה התשע-עשרה אפשר למצוא בספרו של יצחק בשביס-זינגר, עושה הנפלאות מלובלין.
בית העלמין בלובלין.
בית העלמין נמסר כמגרש אחד מבין שלושה מגרשים שנמסרו לקהילה היהודית בלובלין ב-1555, כהרחבת בית הקברות הישן. על שלושת המגרשים נתחייבה הקהילה לשלם מס שנתי של 12 מרקים ומכסה שנתית של חלב נרות. בשנת 1655 נכבשה לובלין על ידי הקוזקים שפרצו אל הרובע היהודי. הם רצחו כעשרת אלפים יהודים ובזזו את העיר. קבוצת יהודים התעטפה בטליתות וביקשה מהקוזאקים לקבור אותם חיים בבית העלמין. הם מילאו את בקשתם. שמות הנרצחים חרותים על החומה המקיפה את בית העלמין. בבית העלמין בלובלין נקברו רבנים ידועי-שם מתקופת הזוהר של העיר, ביניהם: החוזה מלובלין, רבי עזריאל הורוביץ ("ראש הברזל"), רבי יעקב פולק, רבי שלום שכנא מלובלין, רבי שלמה לוריא (מהרש"ל).
ב־1829 נוסד בית הקברות החדש, שנהרס בידי הנאצים, אך שימש לאחר המלחמה כמקום קבורת נפטרי הקהילה.
לובלין שלאחר המלחמה.
בעקבות כיבוש לובלין בידי הצבא האדום, ב-24 ביולי 1944, הגיעו לעיר כחמשת אלפים יהודים, בעיקר כאלה שחיו ברוסיה במהלך המלחמה. בתחילת אוקטובר 1944 נוסדה בעיר "המועצה היהודית" והוגשה בקשה ל"מועצה הפולנית לשחרור לאומי" (PKWN) למנות את הרב ראובן פלדשו כרב ראשי לשארית הפליטה. בעיר נוסד גם מועדון יהודי על שם יצחק לייב פרץ ברחוב לוברטובסקה אשר שימש מרכז החיים של הפליטים היהודים. ב-1944 נוסדה בעיר שלוחה של "החברה ההיסטורית היהודית", ששכנה באותה עת בלודז', ואחר כך עברה לוורשה. בשנים 1946–1950 רבים מיהודי העיר עזבו בגלל האנטישמיות בפולין, שמשיאיה היה פוגרום קיילצה. חיים יהודיים של קהילה נמשכו בעיר עד 1968.
היום בלובלין.