باز کردن منو اصلی

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

مولّد اعداد شبه تصادفی (انگلیسی: Pseudorandom number generator)، که به مولد قطعی (deterministic) اعداد شبه تصادفی نیز، معروف است،[۱] الگوریتمی است که دنباله‌ای از اعداد را که با تقریب خوبی تصادفی هستند، تولید می‌کند. در واقع دنبالهٔ تولیدشده، واقعاً تصادفی نیست، بلکه به‌طور کامل قابل پیش‌بینی، و از روی حالت اولیهٔ الگوریتم، قابل محاسبه‌ است.

مولدهای اعداد تصادفی، مهم و کاربردی هستند. علت کاربرد گستردهٔ آن‌ها، توانایی تولید دوبارهٔ اعداد تولیدشدۀ قبلی و سرعت بالای تولید است. برای همین، از این الگوریتم‌ها در شبیه‌سازی‌ها (مثلاً روش مونت‌کارلورمزنگاری، و بازی‌های کامپیوتری بسیار استفاده می‌شود. بیشتر الگوریتم‌های رمزنگاری نیاز دارند که خروجی‌شان غیرقابل پیش‌بینی باشد و این امر جز با استفاده از اعداد شبه تصادفی، میسر نمی‌شود.


در حالت کلی، بررسی‌های دقیق ریاضی لازم است تا تضمین شود که الگوریتمی، اعدادی تولید می‌کند که تا حد معقولی تصادفی هستند. جان فُون نُویمان به سوءبرداشت از الگوریتم‌های تولیدکنندهٔ اعداد تصادفی، اشاره کرده‌است و هشدار داده که همواره باید به تفاوت آن‌ها توجه کرد.[۲]

تناوبویرایش

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

اگر هر حالت الگوریتم، n بیت داشته‌باشد، دورهٔ تناوب دنبالۀ خروجی آن از ۲n بزرگتر نخواهد بود، حتی ممکن است کمتر هم باشد. برای بعضی از چنین الگوریتم‌هایی می‌توان بدون سپری‌شدن دورهٔ تناوب، دورهٔ تناوب را به دست آورد. مثلاً دورهٔ تناوب خروجی شیفت‌رجیستر فیدبک‌دار خطی n-بیتی، برابر ۱-۲n است. چنین الگوریتم‌هایی با رسیدن به دورهٔ تناوب خود، اعداد تکراری تولید می‌کنند.

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

مشکلات مولدهای قطعیویرایش

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

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

روش‌های اولیهویرایش

یکی از روش‌های اولیهٔ مبتنی بر کامپیوتر، به وسیلهٔ فُون نویمان در سال ۱۹۴۶ ارائه شد. این روش به روش «میان-مربع» (Middle-Square) معروف است («میانِ مربع» یا «مربعِ میانی» خوانده نشود)؛ یک عدد دلخواه در نظر گرفته، آن را به توان ۲ برسانید (مربع کنید)، ۴ رقم میانی آن را به عنوان یک عدد تصادفی جدید در نظر بگیرید و آن‌ را به‌عنوان عدد بعدی در الگوریتم استفاده کنید و به این کار ادامه دهید.

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

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

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

الگوریتم مرسنویرایش

در سال ۱۹۹۷ اختراع الگوریتم مرسن، به وسیلهٔ ماکوتو ماکسوموتو و تاکوجو نیشی‌مورا، بسیاری از ضعف‌های الگوریتم‌های قبلی را برطرف کرد. دورهٔ تناوب این الگوریتم ۱ - ۲۱۹۹۳۷ است (>۴.۳‎×۱۰۶۰۰۱)، که ثابت شده‌است برای خروجی‌های ۳۲ بیتی تا ۶۲۳ بعد، به‌طور یکنواخت، توزیع شده‌است. از طرفی این الگوریتم، از الگوریتم‌های مشابه خود از نظر دقت، بسیار سریع‌تر است. به همین خاطر، روز به روز استفاده از این الگوریتم برای تولید اعداد تصادفی مورد نیاز در شبیه سازی‌ها و مدل سازی‌های مولد رو به افزایش است. همچنین نوع خاصی از این الگوریتم، که برای سیستم‌هایی با توانایی اجرای یک دستور برای تعداد زیادی داده را دارند، وجود دارد که بسیار سریع می‌باشد. پردازش گرهای گرافیکی از این نوع سیستم‌ها محسوب می‌شوند.

الگوریتم مرسن، برای استفاده در نرم‌افزارهای رمز نگاری مناسب نیست. اما ویرایشی از آن وجود دارد که آن را برای این کاربرد بهینه کرده‌است.

مطالعهٔ بیشترویرایش

یادداشت‌هاویرایش

  1. http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf
  2. Peterson, Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6

منابعویرایش

  • Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. A definitive source of techniques for provably random sequences.
  • دانلد کنوت. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3, pp.  1–193. Extensive coverage of statistical tests for non-randomness.
  • R. Matthews Maximally Periodic Reciprocals Bulletin of the Institute of Mathematics and its Applications 28 147-148 1992
  • J. Viega, Practical Random Number Generation in Software, in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
  • John von Neumann, "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds. , Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C. : U.S. Government Printing Office, 1951): 36-38.
  • موسسه ملی فناوری و استانداردها Recommendation for Random Number Generation Using Deterministic Random Bit Generators
  • Luc Devroye (1986). Non-Uniform Random Variate Generation. New York: Springer-Verlag. Archived from the original on 5 May 2009. Retrieved 9 December 2011.

پیوند به بیرونویرایش