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

یک سازنده اعداد شبه تصادفی که به سازنده قطعی بیت‌های شبه تصادفی نیز، معروف است، در واقع به الگوریتمی اطلاق می‌شود که می‌تواند، دنباله‌ای از اعداد تولید نماید به گونه‌ای که، تخمین خوبی از ویژگی‌های اعداد تصافی را داشته باشند. در واقع دنباله تولید شده، تصادفی نمی‌باشد و برای دنباله‌های کوچک به‌طور کامل قابل پیش‌بینی است و از روی حالت اولیه الگوریتم، قابل محاسبه‌است، اما می‌توان با استفاده از تولیدکننده‌های تصادفی سخت افزاری، دنباله‌های عددی بهتری تولید نمود. اعداد تصادفی در عمل بسیار مهم و کاربردی هستند. علت کاربرد گسترده آن را، می‌توان توانایی تولید دوباره اعداد تولید شده در اجراهای قبل و سرعت بالای تولید، ذکر نمود. به همین منظور، از این الگوریتم در شبیه سازی، رمزنگاری و… به وفور استفاده می‌گردد. به‌طور نمونه، اکثر برنامه‌های رمزنگاری نیاز دارند که خروجی شان غیر قابل پیش‌بینی باشد و این امر جز با استفاده از اعداد تصادفی، میسر نمی‌گردد.
در حالت کلی، لازم است بررسی‌های دقیق ریاضی انجام گردد تا تضمین شود الگوریتمی، اعدادی تولید می‌کند که تا حد معقولی تصادفی هستند و استفاده آن‌ها برای کاربردهای دیگر معقول به نظر برسد. ون نیومن به سوء برداشت از الگوریتم‌های تولیدکننده اعداد تصادفی، اشاره کرده‌است و هشدار داده که همواره باید به تفاوت آن‌ها توجه نمود.
تناوب
یک سازنده تصادفی از یک حالت دلخواه اولیه، شروع می‌کند. توجه نمایید چنین سازنده‌ای اگر در اجرای دیگری، از همان حالت اولیه شروع نماید، اعدادی یکسان با اجرای دفعه قبل، تولید خواهد نمود. بیش‌ترین طولی که دنباله تولید شده می‌تواند داشته باشد و الگوریتم بعد از آن به تولید اعداد تکراری خواهد پرداخت، متناسب با تعداد حالات الگوریتم ما می‌باشد، که معمولا با تعداد بیت‌های حالات داخل الگوریتم ما، اندازه‌گیری می‌شود. با این حال، با توجه به این که طول تناوب مابازای اضافه شدن هر بیت حالت، دو برابر می‌شود، معمولا این تناوب آن قدر بزرگ هست که پاسخگوی کاربردهای ما باشد.
اگر تعداد حالات درونی الگوریتم مد نظر، شامل n بیت باشد، دوره تناوب آن از ۲ n بزرگتر نخواهد بود. حتی ممکن است بسیار کمتر باشد. برای بعضی از چنین الگوریتم‌هایی می‌توان بدون سپری کردن کل دوره تناوب، دوره تناوب را به دست آورد.
شیفت دهنده‌های خطی با بازخورد معمولا به خاطر دوره تناوب ۱-۲ n ، انتخاب می‌شوند. گرچه چنین الگوریتم‌هایی با رسیدن به انتهای دوره تناوب خود، اعداد تکراری تولید می‌کنند، اما تولید اعداد تکراری در دنباله تولید شده، نتیجه نمی‌دهد که به انتهای دوره تناوب خود رسیده‌اند، به این خاطر که ممکن است تعداد بیت حالات درونی از تعداد بیت اعداد خروجی بیشتر باشد. چنین اتفاقی برای خروجی‌هایی با یک بیت، به وفور رخ می‌دهد.
اکثر الگوریتم‌های سازنده اعداد شبه تصافی، دنباله‌ای از اعداد تولید می‌نمایند که یک توزیع یکنواخت به ازای هر تعداد عدد تولید شده را، تشکیل می‌دهند. هم اکنون، این سوال که آیا می‌توان تفاوتی بین دنباله‌ای از اعداد تصافی با دنباله‌ای از اعداد شبه تصادفی که با کیفیت خوبی تولید شده‌اند یافت، بدون این که اطلاعی از الگوریتم به کار رفته و حالت اولیه الگوریتم داشته باشیم، هنوز به عنوان سوالی حل نشده باقی مانده‌است. امنیت بیشتر الگوریتم‌های رمزنگاری بر پایه عدم حل چنین مسئله‌ای بنا شده‌است.
مشکلات تولیدکننده‌های قطعی
تجربه نشان می‌دهد، خروجی‌های تولید شده، به علت خطاهای موجود، نمی‌توانند رضایت مطلوبی بدهند و تعدادی کمی از تست‌های آماری را به خوبی بگذرانند. می‌توان در زیر به تعدادی از این نقص‌ها، اشاره نمود.
برای بعضی از حالات اولیه، دوره تناوب بسیار کم‌تر از حد انتظار به دست می‌آید.
در دنباله‌های بزرگ تولید شده به وسیله الگوریتم، توزیع یکنواختی حاصل نمی‌شود.
وجود همبستگی بین اعداد متوالی تولید شده کاملا محسوس می‌باشد.
دنباله‌های خروجی، توزیع غیر یک نواختی دارند.
فاصله بین بعضی مقدارهای خاص، در دنباله تولید شده، بسیار با حالت مشابه تصافی خود، اختلاف دارد.
روش‌های اولیه
یکی از روش‌های اولیه مبتنی بر کامپیوتر، به وسیله ون نیومن در سال ۱۹۴۶ ارائه شد. این روش به روش ریشه میانی معروف است. شرح آن از این قرار است که اگر
یک عدد دلخواه در نظر بگیرید، آن را به توان ۲ برسانید، ۴ رقم میانی آن را به عنوان یک عدد تصادفی در نظر بگیرید و از عدد به دست آمده به عنوان عدد بعدی مورد استفاده در الگوریتم، استفاده کنید. به‌طور مثال با شروع از عدد «۱۱۱۱»، عدد «۱۲۳۴۳۲۱» حاصل می‌شود، که اگر آن را به صورت هشت رقمی بنویسیم، «۰۱۲۳۴۳۲۱» به دست می‌آید. این عدد «۲۳۴۳» را به عنوان یک عدد تصافی به ما می‌دهد. با تکرار این عمل روی عدد «۲۳۴۳» به عدد «۴۸۹۶» به عنوان عدد تصادفی بعدی، خواهیم رسید. می‌توان همین روند را ادامه داد. قابل ذکر است که در روش اصلی از اعداد ۵ رقمی استفاده می‌شد، که روندی کاملا مشابه دارد.
در الگوریتم ارائه شده، پس از طی تعدادی مرحله، به عددی تکراری خواهیم رسید. مشکل اینجاست که به ازای بعضی از اعداد ورودی، به سرعت این اتفاق می‌افتد. به‌طور نمونه، برای عدد «۰۰۰۰». ون نیومن از این مشکل مطلع بود، اما روش ارائه شده برای کاربرد مورد نظر، مناسب بود.
ون نیومن، تولیدکننده‌های سخت افزاری اعداد تصافی را، غیر مناسب می‌دانست. به این خاطر که اگر خروجی‌های تولید شده ذخیره نمی‌شد، بعدا امکان باز تولید آن‌ها وجود نداشت و امکان تست کردن خطا وجود نداشت. در حالتی هم که خروجی‌ها را، ذخیره می‌کردند، حافظه محدود در آن زمان به هدر می‌رفت. اگر اعداد تولید شده، بر روی کارت پانچ، ذخیره می‌شد، زمان خواندن و نوشتن آن‌ها سرسام‌آور می‌شد. به همین منظور استفاده از روش «ریشه میانی» سرعتی صدها برابر از سرعت خواندن و نوشتن از روی کارت پانچ، را داشت.
از آن به بعد، این روش در جاهای مختلفی و به وسیله افراد مختلفی، استفاده شد.
الگوریتم مرسن
در سال ۱۹۹۷ اختراع الگوریتم مرسن، به وسیله ماکوتو ماکسوموتو و تاکوجو نیشیمورا، بسیاری از ضعف‌های الگوریتم‌های قبلی را برطرف نمود. دوره تناوب این الگوریتم ۱ - ۲ ۱۹۹۳۷ است (>۴.۳)، که ثابت شده‌است برای خروجی‌های ۳۲ بیتی تا ۶۲۳ بعد، به‌طور یکنواخت، توزیع شده‌است. از طرفی این الگوریتم، از الگوریتم‌های مشابه خود از نظر دقت، بسیار سریع‌تر است. به همین خاطر، روز به روز استفاده از این الگوریتم برای تولید اعداد تصادفی مورد نیاز در شبیه سازی‌ها و مدل سازی‌های مولد رو به افزایش است. همچنین نوع خاصی از این الگوریتم، که برای سیستم‌هایی با توانایی اجرای یک دستور برای تعداد زیادی داده را دارند، وجود دارد که بسیار سریع می‌باشد. پردازش گرهای گرافیکی از این نوع سیستم‌ها محسوب می‌شوند.
الگوریتم مرسن، برای استفاده در نرم‌افزارهای رمز نگاری مناسب نمی‌باشد. اما ویرایشی از آن وجود دارد که آن را برای این کاربرد بهینه نموده‌است.
مطالعه بیشتر
لیست از الگوریتم‌ها، برای تولید اعداد شبه تصادفی
اعداد دودویی شبه تصادفی
اعداد رندم کواسی
حملات مخرب با ساخت اعداد تصادفی
تصادفی بودن