عدد شبه تصادفی عدد خاصی است که توسط یک مولد خاص تولید می شود. مولد بیت های تصادفی قطعی (PRNG) که با نام مولد بیت های تصادفی قطعی (DRBG) نیز شناخته می شود، الگوریتمی برای تولید دنباله ای از اعداد است که ویژگی های آن ها تقریباً ویژگی های دنباله های اعداد تصادفی است. توالی PRNG تولید شده واقعاً تصادفی نیست، زیرا کاملاً توسط یک مقدار دانه به نام دانه PRNG تعیین می شود که ممکن است شامل مقادیر واقعاً تصادفی باشد. اگرچه توالی‌هایی که به تصادفی نزدیک‌تر هستند را می‌توان با استفاده از مولدهای اعداد تصادفی سخت‌افزاری تولید کرد، مولدهای اعداد شبه تصادفی در عمل برای سرعت تولید اعداد و تکرارپذیری آنها مهم هستند.
برنامه
PRNG ها برای برنامه هایی مانند شبیه سازی (مثلاً برای مونت کارلو)، بازی های الکترونیکی (مثلاً برای تولید رویه ای)، و رمزنگاری مرکزی هستند. برنامه های رمزنگاری نیاز به خروجی دارندداده ها از اطلاعات قبلی قابل پیش بینی نبود. الگوریتم های پیچیده تری مورد نیاز است که خطی بودن PRNG های ساده را به ارث نمی برند.
شرایط و ضوابط
خواص آماری خوب یک نیاز اصلی برای به دست آوردن یک PRNG است. به طور کلی، تجزیه و تحلیل ریاضی دقیق مورد نیاز است تا مطمئن شویم که RNG اعدادی را تولید می کند که به اندازه کافی به تصادفی نزدیک هستند تا برای استفاده مورد نظر مناسب باشند.
جان فون نویمان نسبت به تفسیر نادرست PRNG به عنوان یک مولد واقعاً تصادفی هشدار داد و به شوخی گفت: "هرکسی که روش های حسابی را برای تولید اعداد تصادفی در نظر می گیرد، مطمئناً در حالت گناه است."
استفاده
PRNG را می توان از یک حالت اولیه دلخواه راه اندازی کرد. هنگامی که با این حالت مقداردهی اولیه شود، همیشه همان دنباله را ایجاد می کند. دوره PRNG به صورت زیر تعریف می شود: حداکثر در تمام حالت های اولیه طول پیشوند توالی غیر تکراری. دوره با تعداد حالت ها محدود می شود که معمولاً در بیت اندازه گیری می شود. از آنجایی که طول دوره به طور بالقوه با افزودن هر بیت "وضعیت" دو برابر می شود، ایجاد PRNG با دوره های به اندازه کافی برای بسیاری از کاربردهای عملی آسان است.
اگر حالت داخلی PRNG حاوی n بیت باشد، دوره آن نمی تواند بیشتر از 2n نتیجه باشد، بسیار کوتاهتر است. برای برخی از PRNG ها، مدت زمان را می توان بدون دور زدن کل دوره محاسبه کرد. رجیسترهای تغییر بازخورد خطی (LFSR) معمولاً هستندطوری انتخاب می شوند که دوره هایی برابر با 2n − 1 داشته باشند.
مولدهای همگرای خطی دارای دوره هایی هستند که می توان آنها را با استفاده از فاکتورگیری محاسبه کرد. اگرچه PPP نتایج خود را پس از رسیدن به پایان دوره تکرار خواهد کرد، اما تکرار نتیجه به معنای رسیدن به پایان دوره نیست، زیرا وضعیت داخلی آن ممکن است بیشتر از خروجی باشد. این به ویژه برای PRNG با خروجی تک بیت مشهود است.
خطاهای احتمالی
خطاهایی که توسط PRNG های معیوب یافت می شوند از موارد ظریف (و ناشناخته) تا آشکار متغیر هستند. به عنوان مثال الگوریتم اعداد تصادفی RANDU است که برای چندین دهه در مین فریم ها استفاده شده است. این یک نقص جدی بود، اما نارسایی آن برای مدت طولانی مورد توجه قرار نگرفت.
در بسیاری از زمینه‌ها، مطالعات تحقیقاتی که از انتخاب تصادفی، شبیه‌سازی مونت کارلو یا سایر روشهای مبتنی بر RNG استفاده کرده‌اند، بسیار کمتر از آن چیزی هستند که می‌تواند نتیجه GNPG با کیفیت پایین باشد. حتی امروزه نیز گاهی احتیاط لازم است، همانطور که با هشدار در دایره المعارف بین المللی علوم آماری (2010) مشهود است.
مطالعه موردی موفق
به عنوان مثال، زبان برنامه نویسی جاوا را در نظر بگیرید. از سال 2017، جاوا همچنان برای PRNG خود به ژنراتور هماهنگ خطی (LCG) متکی است.
تاریخ
اولین PRNG برای جلوگیری از مشکلات جدی و همچنان بسیار سریع اجرا می شود،Mersenne Twister (در زیر مورد بحث قرار می گیرد) بود که در سال 1998 منتشر شد. از آن زمان، سایر PRNG های با کیفیت بالا توسعه یافته اند.
اما تاریخچه اعداد شبه تصادفی به همین جا ختم نمی شود. در نیمه دوم قرن بیستم، کلاس استاندارد الگوریتم های مورد استفاده برای PRNG ها شامل ژنراتورهای همخوانی خطی بود. کیفیت LCG ناکافی شناخته شد، اما روش های بهتری در دسترس نبود. پرس و همکاران (2007) نتیجه را به شرح زیر توصیف کردند: "اگر تمام مقالات علمی که نتایج آنها به دلیل [LCG و مرتبط] مورد تردید است از قفسه های کتابخانه ناپدید شوند، شکافی به اندازه مشت شما در هر قفسه وجود خواهد داشت."
دستاورد اصلی در ایجاد ژنراتورهای شبه تصادفی، معرفی روش‌هایی مبتنی بر بازگشت خطی در یک میدان دو عنصری بود. چنین نوسانگرهایی به رجیسترهای تغییر بازخورد خطی جفت می شوند. آنها به عنوان مبنایی برای اختراع حسگرهای اعداد شبه تصادفی عمل کردند.
به ویژه، اختراع 1997 توسط Mersen Twister از بسیاری از مشکلات ژنراتورهای قبلی جلوگیری کرد. Mersenne Twister دارای یک دوره 219937-1 تکرار (≈4.3 × 106001) است. ثابت شده است که به طور یکنواخت در (تا) 623 بعد (برای مقادیر 32 بیتی) توزیع شده است، و در زمان معرفی سریعتر از سایر مولدهای آماری سالم بود که دنباله های اعداد شبه تصادفی تولید می کنند.
در سال 2003، جورج مارسالیا خانواده ای از ژنراتورهای xorshift را نیز بر اساس تکرار خطی معرفی کرد. این ژنراتورها فوق العاده هستندسریع هستند و - همراه با یک عملیات غیر خطی - تست های آماری دقیقی را پشت سر می گذارند.
در سال 2006، خانواده ژنراتور WELL توسعه یافت. ژنراتورهای WELL به یک معنا کیفیت Twister Mersenne را بهبود می‌بخشند که فضای حالت بسیار بزرگ و بازیابی بسیار آهسته از آنها دارد و اعداد شبه تصادفی با تعداد زیادی صفر تولید می‌کند.
رمز نگاری
PRNG مناسب برای کاربردهای رمزنگاری، PRNG امن رمزنگاری (CSPRNG) نامیده می شود. شرط لازم برای CSPRNG این است که مهاجمی که seed را نمی شناسد فقط یک مزیت حاشیه ای در تشخیص دنباله خروجی مولد از یک دنباله تصادفی داشته باشد. به عبارت دیگر، در حالی که یک PRNG فقط برای گذراندن آزمایش‌های آماری خاص مورد نیاز است، یک CSPRNG باید تمام آزمون‌های آماری را که به زمان چند جمله‌ای در اندازه دانه محدود می‌شوند، پاس کند.
اگرچه اثبات این ویژگی فراتر از سطح فعلی نظریه پیچیدگی محاسباتی است، شواهد قوی را می توان با تقلیل CSPRNG به مسئله ای که سخت در نظر گرفته می شود، مانند فاکتورسازی اعداد صحیح، ارائه کرد. به طور کلی، ممکن است قبل از تایید الگوریتم به عنوان CSPRNG، سال ها بررسی لازم باشد.
نشان داده شده است که این احتمال وجود دارد که NSA یک در پشتی نامتقارن را در مولد اعداد شبه تصادفی Dual_EC_DRBG دارای گواهینامه NIST قرار داده باشد.
الگوریتم های شبه تصادفیاعداد
اکثر الگوریتم‌های PRNG توالی‌هایی تولید می‌کنند که با هر یک از چندین آزمایش به طور مساوی توزیع می‌شوند. این یک سوال باز است. این یکی از محورهای تئوری و عمل رمزنگاری است: آیا راهی برای تشخیص خروجی یک PRNG با کیفیت بالا از یک توالی واقعاً تصادفی وجود دارد؟ در این تنظیمات، حل‌کننده می‌داند که یا از یک الگوریتم شناخته شده PRNG استفاده شده است (اما نه حالتی که با آن مقداردهی اولیه شده است)، یا از یک الگوریتم واقعاً تصادفی استفاده شده است. او باید بین آنها تمایز قائل شود.
امنیت بیشتر الگوریتم‌ها و پروتکل‌های رمزنگاری که از PRNG استفاده می‌کنند بر این فرض استوار است که تمایز بین استفاده از یک PRNG مناسب و استفاده از یک دنباله واقعاً تصادفی غیرممکن است. ساده‌ترین نمونه‌های این وابستگی، رمزهای جریانی هستند که اغلب با حذف یا ارسال پیام متن ساده با خروجی PRNG کار می‌کنند و متن رمز را تولید می‌کنند. طراحی PRNG های رمزنگاری مناسب بسیار دشوار است زیرا باید معیارهای اضافی را رعایت کنند. اندازه دوره آن یک عامل مهم در مناسب بودن رمزنگاری یک PRNG است، اما تنها عامل نیست.
یک PRNG کامپیوتر اولیه که توسط جان فون نویمان در سال 1946 پیشنهاد شد به عنوان روش مربعات میانگین شناخته می شود. الگوریتم به این صورت است: هر عددی را بگیرید، مربع آن را ببرید، ارقام میانی عدد حاصل را به عنوان یک "عدد تصادفی" حذف کنید، سپس از این عدد به عنوان عدد شروع برای تکرار بعدی استفاده کنید. به عنوان مثال، مربع کردن عدد 1111 می دهد1234321 که می توان آن را 01234321 نوشت، یک عدد 8 رقمی مربع یک عدد 4 رقمی است. این عدد 2343 را به عنوان یک عدد "تصادفی" به دست می دهد. نتیجه تکرار این روش 4896 و به همین ترتیب است. فون نیومن از اعداد 10 رقمی استفاده کرد، اما روند یکسان بود.
معایب "مربع وسط"
مشکل در روش "میانگین مربع" این است که همه دنباله ها در نهایت تکرار می شوند، برخی از آنها خیلی سریع، به عنوان مثال: 0000. فون نویمان از این موضوع می دانست، اما او رویکردی را برای اهداف خود کافی یافت و نگران بود که "اصلاحات" ریاضی به جای حذف اشتباهات، فقط آنها را پنهان می کند.
فون نیومن مولدهای اعداد تصادفی و شبه تصادفی سخت‌افزاری را نامناسب تشخیص داد: اگر خروجی تولید شده را ضبط نکنند، بعداً نمی‌توان آنها را برای خطا بررسی کرد. اگر قرار بود نتایج خود را یادداشت کنند، حافظه محدود موجود کامپیوتر و در نتیجه توانایی کامپیوتر برای خواندن و نوشتن اعداد را تمام می‌کنند. اگر اعداد روی کارت ها نوشته می شد، نوشتن و خواندن آنها بسیار بیشتر طول می کشید. او در رایانه ENIAC از روش "مربع وسط" استفاده کرد و فرآیند بدست آوردن اعداد شبه تصادفی را چندین صد برابر سریعتر از خواندن اعداد از کارت های پانچ انجام داد.
معادل مربع از آن زمان با ژنراتورهای پیچیده تر جایگزین شده است.
روش ابتکاری
یک نوآوری اخیر ترکیب مربع میانگین با دنباله ویل است. این روش محصولات با کیفیت بالا را در داخل تضمین می کندزمان طولانی. به دست آوردن بهترین فرمول های اعداد شبه تصادفی کمک می کند.
