نشریه‌ی الکترونیکی رایانا

چگونه رایانه ها اعداد تصادفی تولید می کنند؟

در ابتدا ببینیم که اعداد تصادفی به چه دردی می خورند.

اعداد تصادفی برای چه کارهایی استفاده می شود؟

رایانه ها اعداد تصادفی را برای کاربردهای مختلف، از رمزنگاری گرفته تا بازی‌های رایانه ای، تولید می‌کنند.

هزاران سال است که از اعداد تصادفی استفاده می‌شود. چه این کار از طریق پرتاب سکه رخ دهد و چه از طریق پرتاب تاس انجام بگیرد، هدف این است که نتیجه نهایی به صورت تصادفی به دست آمده باشد.

تولیدکننده‌های اعداد تصادفی در رایانه ها نیز به همین شکل هستند. در واقع آن ها به دنبال به دست آوردن نتایج غیرقابل‌ پیش‌بینی و تصادفی هستند.

تولیدکننده‌ های اعداد تصادفی برای کاربردهای مختلفی مفید هستند. به غیر از کاربردهای واضحی مثل ایجاد شرایط غیرقابل‌ پیش‌بینی در بازی‌های رایانه ای، تصادفی بودن در رمزنگاری بسیار مهم است.

رمزنگاری به اعدادی نیاز دارد که مهاجمان نتوانند آن ها را حدس بزنند. مشخص است که نمی‌توانیم به‌طور مداوم از اعدادی مشخص استفاده کنیم. هدف ما این است که این اعداد را به طریقی کاملا غیرقابل‌ پیش‌بینی تولید کنیم تا مهاجمان نتوانند آن‌ها را حدس بزنند. این اعداد تصادفی چه برای یک رمزنگاری ایمن، چه برای رمزنگاری فایل‌های شخصی خودتان باشد و چه برای استفاده از یک وب‌سایت در اینترنت، کاملا ضروری هستند.

شاید برای شما سوال شده باشد که یک رایانه چگونه می‌تواند یک عدد تصادفی تولید کند. این “تصادفی بودن” از کجا می‌آید؟ اگر این تولیدکننده تنها یک کد رایانه ای است، آیا ممکن نیست که اعداد تصادفی که تولید می‌کند قابل پیش‌بینی باشند؟

به طور کلی اعداد تصادفی به دو دسته اعداد تصادفی واقعی و اعداد شبه تصادفی تقسیم می شوند.

اعداد تصادفی واقعی

برای تولید یک عدد تصادفی واقعی، رایانه نوعی پدیده فیزیکی را که در بیرون از آن رخ می‌دهد، اندازه‌گیری می‌کند. برای مثال،​ یک رایانه می‌تواند واپاشی هسته‌ای یک اتم را اندازه‌گیری کند. مطابق نظریه کوانتوم،​ هیچ راهی وجود ندارد که بتوان به‌طور قطعی دانست واپاشی هسته‌ای در چه زمانی اتفاق می‌افتد. پس این درواقع، “تصادفی بودن خالص” ناشی از جهان هستی است. یک مهاجم نمی‌تواند پیش‌بینی کند که واپاشی هسته‌ای در چه زمانی اتفاق می‌افتد، پس نمی‌تواند آن مقدار تصادفی را نیز پیدا کند.

به‌عنوان یک مثال آشناتر، رایانه ها می‌توانند از بانگ های جوی یا حتی ساده‌تر از آن،​ از زمان دقیق فشار دادن دکمه‌های کیبورد به‌عنوان منبع داده‌های غیرقابل‌ پیش‌بینی، استفاده کنند. برای مثال، ممکن است رایانه شما فشرده شدن یک کلید در دقیقا ۰.۲۳۴۲۳۵۲۳ ثانیه پس از ساعت ۲ بعد از ظهر را ثبت کند. با جمع‌آوری تعداد کافی از زمان‌های مربوط به فشرده شدن کلیدها، یک منبع غیر قابل پیش بینی خواهید داشت که می‌توانید از آن برای تولید یک عدد تصادفی واقعی استفاده کنید. شما  یک دستگاه قابل پیش‌بینی نیستید، پس فرد مهاجم نمی‌تواند زمان دقیق فشرده شدن کلیدهای کیبورد توسط شما را حدس بزند. دستگاه  /dev/random، که در لینوکس اعداد تصادفی تولید می‌کند، تا زمانی که داده های غیر قابل پیش بینی کافی برای تولید یک عدد تصادفی واقعی به دست نیاورد، درخواست‌های کاربر را رد کرده و نتیجه‌ای نمایش نمی‌دهد.

اعداد شبه تصادفی

مولّد اعداد شبه تصادفی که به مولد قطعی اعداد شبه تصادفی نیز معروف است،الگوریتمی است که دنباله‌ای از اعداد را که با تقریب خوبی  تصادفی هستند، تولید می‌کند. در واقع دنبالهٔ تولیدشده، واقعاً تصادفی نیست، بلکه به‌طور کامل قابل پیش‌بینی، و  از روی حالت اولیهٔ الگوریتم، قابل محاسبه‌ است.

مولدهای اعداد تصادفی، مهم و کاربردی هستند. علت کاربرد گستردهٔ آن‌ها، توانایی تولید دوبارهٔ اعداد تولیدشدۀ قبلی و سرعت بالای تولید است. برای همین، از این الگوریتم‌ها در شبیه‌سازی‌ها ,رمزنگاری و بازی‌های رایانه ای بسیار استفاده می‌شود.

در حالت کلی، بررسی‌های دقیق ریاضی لازم است تا تضمین شود که الگوریتمی، اعدادی تولید می‌کند که تا حد معقولی تصادفی هستند.

روش میان مربع برای تولید اعداد تصادفی

یکی از روش‌های اولیهٔ به وسیلهٔ فُون نویمان در سال ۱۹۴۶ ارائه شد. این روش به روش «میان-مربع» معروف است .

یک عدد دلخواه در نظر گرفته، آن را به توان ۲ برسانید (مربع کنید)، ۴ رقم میانی آن را به عنوان یک عدد تصادفی جدید در نظر بگیرید و آن‌ را به‌عنوان عدد بعدی در الگوریتم استفاده کنید و به این کار ادامه دهید.

مثلاً با شروع از عدد ۱۱۱۱، عدد ۱۲۳۴۳۲۱ حاصل می‌شود، که اگر آن را به صورت هشت رقمی بنویسیم، ۰۱۲۳۴۳۲۱ به دست می‌آید. عدد ۲۳۴۳ به عنوان یک عدد تصادفی به دست می‌آید. با تکرار این عمل روی ۲۳۴۳ به ۴۸۹۶ به عنوان عدد تصادفی بعدی خواهیم رسید. می‌توان همین روند را ادامه داد. 

در این الگوریتم، پس از تعدادی مرحله به عددی تکراری خواهیم رسید. مشکل اینجاست که به‌ازای بعضی از اعداد ورودی، این اتفاق به سرعت می‌افتد.

فون نویمان، تولیدکننده‌های سخت‌افزاری اعداد تصادفی را غیرمناسب می‌دانست. چراکه اگر خروجی‌های تولیدشده ذخیره نمی‌شد، بعداً امکان بازتولید آن‌ها و امتحان کردن خطا وجود نداشت. در حالتی هم که خروجی‌ها را ذخیره می‌کردند، حافظه به هدر می‌رفت. اگر اعداد تولیدشده ذخیره می‌شد، زمان خواندن و نوشتن آن‌ها  طولانی می‌شد، درحالی‌که استفاده از روش «میان-مربع» سرعتی صدها برابر بیشتر از سرعت روش قبلی را داشت.