موضوع مقاله: مولد اعداد شبه تصادفی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مولد اعداد شبه تصادفی | مقدمه: در واقع دنبالهٔ تولیدشده، واقعاً تصادفی نیست، بلکه به‌طور کامل قابل پیش‌بینی، و از روی حالت اولیهٔ الگوریتم، قابل محاسبه است. | ## بخش 1: مولد اعداد شبه تصادفی | علت کاربرد گستردهٔ آن‌ها، توانایی تولید دوبارهٔ اعداد تولیدشدهٔ قبلی و سرعت بالای تولید است. برای همین، از این الگوریتم‌ها در شبیه‌سازی‌ها (مثلاً روش مونت‌کارلو)، رمزنگاری، و بازی‌های کامپیوتری بسیار استفاده می‌شود. بیشتر الگوریتم‌های رمزنگاری نیاز دارند که خروجی‌شان غیرقابل پیش‌بینی باشد و این امر جز با استفاده از اعداد شبه تصادفی، میسر نمی‌شود. در حالت کلی، بررسی‌های دقیق ریاضی لازم است تا تضمین شود که الگوریتمی، اعدادی تولید می‌کند که تا حد معقولی تصادفی هستند. جان فُون نُویمان به سوءبرداشت از الگوریتم‌های تولیدکنندهٔ اعداد تصادفی، اشاره کرده‌است و هشدار داده که همواره باید به تفاوت آن‌ها توجه کرد. مشکلات بالقوه با مولدهای قطعی تجربه نشان می‌دهد خروجی‌های تولیدشده، به علت خطاهای موجود، راضی‌کننده نیستند و تعداد کمی از تست‌های آماری را به خوبی می‌گذرانند. می‌توان به تعدادی از این نقص‌ها، اشاره کرد؛ برای بعضی از حالات اولیه، دوره تناوب کمتر از حد انتظار است. فاصلهٔ بعضی مقدارهای خاص، در دنبالهٔ تولید شده، با حالت مشابه تصادفی خود، بسیار اختلاف دارد. مولدهای اعداد شبه تصادفی نقص‌های زیادی داشتند از نقص‌هایی که زیاد قابل توجه نبود گرفته تا نقص‌های بسیار آشکار. برای مثال RANDU که یک الگوریتم تولید اعداد تصادفی است که دهه‌ها برای بزرگ‌رایانه استفاده می‌شد. این الگوریتم نقص‌های فراوانی داشت، با این وجود برای مدت بسیاری طولانی این نقص‌ها کشف نشدند. در بسیار از زمینه‌ها، تحقیقاتی قبل از قرن بیست و یکم صورت گرفت که در آنها به انتخاب تصادفی یا شبیه‌سازی مونت کارلو متکلی بوده‌اند یا به روش‌های دیگر وابسته به PRNGها بودند. (2007), chap.7 حتی امروزه، برای احتیاط لازم است، هشداری که در زیر نشان داده شده‌است که در دایرةالمعارف بین‌المللی علوم آماری ۲۰۱۰ آمده‌است را نیز جدی گرفت. مواردی از مولدهایی که باید بلااستفاده شوند و دور ریخته شوند بسیار بیشتر از مولدهایی های خوب است؛ بنابراین به فروشندگان نرام افزار بدون آگاهی اعتماد نکنید. برای درک بهتر، زبان‌های برنامه‌نویسی را که به‌طور گسترده استفاده می‌شود را درنظر بگیرید. یکی از مولدهای اعداد شبه تصادفی شناخته شده برای جلوگیری از بروز مشکلات بنیادی و همچین داشتن قابلیت اجرای نسبتاً سریع، مرسن توئیستر (در ادامه مورد بحث است) بود که در سال ۱۹۹۸ منتشر شد. سایر مولدهای تولید اعداد شبه تصادفی که کیفیت بالاتری در جهات محاسبات و کارایی آماری داشتند، قبل و بعد از این تاریخ توسعه یافتند. مولد برمبنای بازگشتی‌های خطی در نیمهٔ دوم قرن بیستم، الگوریتم‌های کلاس استانداری که برای PRNGها استفاده می‌شد، مولدهای سازگار خطی را تشکیل می‌داد. (2007) §7.1 هنگامی پیشرفت اصلی در ساخت مولدهای اعداد شبه تصادفی به‌وجود آمد که تکنیک‌های مبتنی بر بازگشت خطی پدیدآمدند. هنگامی پیشرفت اصلی در ساخت مولدهای اعداد شبه تصادفی به‌وجود آمد که تکنیک‌های مبتنی بر بازگشت خطی پدیدآمدند. به‌طور ویژه اختراع مرسن چرخان، در سال ۱۹۹۷، از بسیار از مشکلات مولدهای پیشین جلوگیری کرد. | ## بخش 2: مولد اعداد شبه تصادفی | مرسن چرخان دوره ای از تکرار (≈۴٫۳×106001)را دارد که ثابت شده‌است در ۶۲۳ بعد (برای اعدا ۳۲ بیتی) توزیع شده‌است. چنین مولدهایی بسیار سریع هستند و به همراه عملیات‌های غیرخطی آزمایش‌های آماری قوی و سختی را پشت سر گذاشتند.Vigna S. یک الزام برای CSPRNG این است که طرفی که seed را نداند، تنها شانس بسیار ناچیزی برای تشخیص و تمایز توالی خروجی مولد از یک دنباله تصادفی دارد. گرچه اثبات این خاصیت فراتر از توانایی فعلی نظریه پیچیدگی محاسباتی است، اما ممکن است با کاهش CSPRNG به مسئله ای که فرض بر آن است که از لحاظ محاسباتی سخت است، مانند فاکتورسازی عدد صحیح، شواهد محکمی بدست آید. به‌طور کلی، ممکن سالها بررسی برای اینکه یک الگوریتم به عنوان CSPRNG تأیید شود، مورد نیاز باشد. برخی از کلاس‌های CSPRNG شامل موارد زیر است: رمزهای دنباله ای رمزگذارهای قالبی که در مدهای کاری رمزهای قطعه‌ای یا در حالت بازخورد خروجی عمل می‌کنند. نشان داده شده‌است که به احتمال زیاد آژانس امنیت ملی آمریکا یک درپشتی نامتقارن به NIST قرار داده بود. اکثر الگوریتم‌های PRNG توالی‌هایی تولید می‌کنند که به طور یکنواخت توسط آزمون‌های گوناگون توزیع می‌شوند. این یک سؤال بدون پاسخ است، و یک موضوع اصلی برای تئوری و عمل رمزنگاری است که آیا راهی برای تمایز خروجی یک PRNG با کیفیت بالا از یک دنباله واقعاً تصادفی وجود دارد؟ در این تنظیم، تشخیص دهنده می‌داند که یا از الگوریتم شناخته شده PRNG استفاده شده‌است (اما نه وضعیتی که با آن آغاز شد) یا از یک الگوریتم واقعاً تصادفی استفاده شده‌است، و باید بین این دو تفاوت قایل شود. امنیت اکثر الگوریتم‌های رمزنگاری و پروتکل‌های با استفاده از PRNG برفرض آن بناشده اند که تشخیص استفاده از PRNG مناسب از استفاده از یک توالی واقعاً غیرممکن است. ساده‌ترین نمونه‌های این وابستگی، رمزنگاری‌های جریانی هستند، که (اغلب) با یای انحصاری بین متن ساده (رمزنشده) پیام و خروجی PRNG کار می‌کنند و متن رمزشده را تولید می‌کنند. طراحی PRNGهای مناسب از نظر رمزنگاری بسیار دشوار است زیرا آنها باید معیارهای بیشتری را رعایت کنند. اندازه دورهٔ تناوب آنها یک عامل مهم تعیین میزان مناسب بودن رمزنگاری یک PRNG است، اما به تنهایی کافی نیست. این موارد به صورت زیر خلاصه می‌شوند: K1 - احتمال متفاوت بودن اعداد متوالی تولید شده از یکدیگر، زیاد است. K2 -اعداد متوالی تولید شده طبق آزمون‌های مخصوص آماری، از اعداد " واقعا تصادفی " قابل تشخیص نیست. در اصل این نیازمندی‌ها جهت ارزیابی کیفیت دنبالهٔ بیت‌ها هستند: آیا تعداد صفرها و یک‌ها اکثراً مساوی است؟ بعد از دنباله ای از صفرهای متوالی (یا یک‌های متوالی) بیت یک بعدی (یا صفر بعدی) با احتمال ۰٫۵ ظاهر می‌شود؟ آیا هر زیرمجموعهٔ انتخاب شده از بیت‌ها اطلاعاتی دربارهٔ بیت یا بیت‌های بعدی می‌دهند؟ K3 - برای مهاجمان در حالت واقعی و عملی، غیرممکن باشد که از هر زیرمجموعه از بیت‌ها هرگونه اطلاعی از مقادیر قبلی یا بعدی را محاسبه کند یا اینکه حالت فعلی مولد را تعیین کند. K4 - برای هر منظور و هدف عملی غیرممکن باشد که مهاجم بتواند از حالت درونی مولد هرعدد قبلی در دنبالهٔ اعداد تولید شده یا حالت قبلی مولد را محاسبه کند یا حدس بزند. | ## بخش 3: مولد اعداد شبه تصادفی | برای کاربردهای رمزنگاری، فقط مولدهایی که موارد K3 و K4 را رعایت کنند، قابل قبول می‌باشند. تعریف ریاضی داده شده (در صورتی که) - توزیع احتمال (جایی که مجموعه استاندارد Borel بر روی خط واقعی است) - مجموعه ای غیر تهی از مجموعه‌های بورل ، به عنوان مثال . غالباً یک مجموعه بین تکیه گاه و درون (توپولوژی) آن؛ به عنوان مثال، اگر توزیع یکنواخت در فاصله باشد، می‌تواند باشد. اگر مشخص نشده باشد، فرض بر این است که مجموعه ای است که همهٔ اعضایش در تکیه گاه موجود اند و شامل توپولوژی اش می‌باشد. ما یک تابع (جایی که مجموعه اعداد صحیح مثبت است) را یک مولد عدد شبه تصادفی برای به طوری که مقادیر را می‌گیرد مینامیم اگر و تنها اگر ( نشان دهنده تعداد اعضای مجموعه متناهی S است) می‌توان نشان داد که اگر مولد عدد شبه تصادفی برای توزیع یکنواخت بر روی بازهٔ باشد و اگر تابع توزیع تجمعی برای توزیع توزیع احتمالی داده شده باشد، سپس مولد اعداد شبه تصادفی برای است، به طوری که صدک است، یعنی . به‌طور شهودی، یک توزیع دلخواه می‌تواند توسط یک توزیع استاندارد یکنواخت شبیه‌سازی شود. رویکردهای اولیه یکی از روش‌های اولیهٔ مبتنی بر کامپیوتر، به وسیلهٔ فُون نویمان در سال ۱۹۴۶ ارائه شد. این روش به روش «میان-مربع» (Middle-Square) معروف است («میانِ مربع» یا «مربعِ میانی» خوانده نشود)؛ یک عدد دلخواه در نظر گرفته، آن را به توان ۲ برسانید (مربع کنید)، ۴ رقم میانی آن را به عنوان یک عدد تصادفی جدید در نظر بگیرید و آن را به‌عنوان عدد بعدی در الگوریتم استفاده کنید و به این کار ادامه دهید. مثلاً با شروع از عدد ۱۱۱۱، عدد ۱۲۳۴۳۲۱ حاصل می‌شود، که اگر آن را به صورت هشت رقمی بنویسیم، ۰۱۲۳۴۳۲۱ به دست می‌آید. فون نویمان از این مشکل مطلع بود، اما روش ارائه‌شده برای کاربرد موردنظر، کافی بود. چراکه اگر خروجی‌های تولیدشده ذخیره نمی‌شد، بعداً امکان بازتولید آن‌ها و تست‌کردن خطا وجود نداشت. اگر اعداد تولیدشده روی کارت پانچ ذخیره می‌شد، زمان خواندن و نوشتن آن‌ها طولانی می‌شد، درحالی‌که استفاده از روش «میان-مربع» سرعتی صدها برابر بیشتر از سرعت خواندن و نوشتن از کارت پانچ داشت. این روش در مدت زمان طولانی تولید خروجی به کیفیت بالا دست میابد (رجوع کنید به توالی PRNG دنباله میدانی Weyl). مولدهای غیر یکنواخت تعداد انتخاب شده از توزیع احتمال غیر یکنواخت را می‌توان با استفاده از یک توزیع PRNG یکنواخت و تابعی که مربوط به این دو توزیع باشد، تولید کرد. اعداد انتخاب شده از یک توزیع احتمالاتی غیریکنواخت می‌تواند توسط یک توزیع یکنواخت PRNG و یک تابع که دو توزیع را به هم مرتبط کند، تولید شود. ابتدا به تایع توزیع تجمعی نیاز داریم توزیع هدف (تابع F توزیع تجمعی f است): توجه داشته باشید که . با استفاده از عدد تصادفی c که از توزیع یکنواخت آمده‌است، به عنوان چگالی احتمال، دریافت می‌کنیم: در نتیجه عددی است که به‌طور تصادفی از توزیع انتخاب شده‌است. به‌طور مثال، وارونه توزیع گاوسی تجمعی با یک PRNG یکنواخت ایده‌آل با دامنه (۰، ۱) که ورودی توالی از مقادیر (فقط مثبت) با توزیع گاوسی را تولید می‌کند. با این حال زمانی که از نمایش عدد عملی استفاده می‌کنیم، "دم"‌های نامتناهی توزیع باید به مقادیر محدود قطع شوند. محاسبه تکراری باید از طریق الگوریتم زیگورات صورت بگیرد تا تولید اعداد سریع تر شود. ملاحظات مشابهی برای تولید توزیع‌های غیر یکنواخت دیگر مانند ریلی و پواسون صورت می‌گیرد. | ## جمع‌بندی | ، مونت کارلو متد، دفتر ملی استاندارد استانداردهای ریاضیات کاربردی، ۱۲ (واشینگتن، دی سی: دولت ایالات متحده دفتر چاپ، ۱۹۵۱): ۳۶–۳۸.