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

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از ساخت اعداد شبه تصادفی)
پرش به: ناوبری، جستجو

یک سازندهٔ اعداد شبه تصادفی که به سازندهٔ قطعی بیت‌های شبه تصادفی نیز، معروف است،[۱] در واقع به الگوریتمی اطلاق می‌شود که می‌تواند، دنباله‌ای از اعداد تولید نماید به گونه‌ای که، تخمین خوبی از ویژگی‌های اعداد تصافی را داشته باشند. در واقع دنبالهٔ تولید شده، تصادفی نمی‌باشد و برای دنباله‌های کوچک به طور کامل قابل پیش بینی است و از روی حالت اولیهٔ الگوریتم، قابل محاسبه‌است، اما می‌توان با استفاده از تولید کننده‌های تصادفی سخت افزاری، دنباله‌های عددی بهتری تولید نمود. اعداد تصادفی در عمل بسیار مهم و کاربردی هستند. علت کاربرد گستردهٔ آن را، می‌توان توانایی تولید دوبارهٔ اعداد تولید شده در اجراهای قبل و سرعت بالای تولید، ذکر نمود. به همین منظور، از این الگوریتم در شبیه سازی، رمزنگاری و... به وفور استفاده می‌گردد. به طور نمونه، اکثر برنامه‌های رمزنگاری نیاز دارند که خروجی شان غیر قابل پیش بینی باشد و این امر جز با استفاده از اعداد تصادفی، میسر نمی‌گردد.

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

تناوب[ویرایش]

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

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

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

مشکلات تولید کننده‌های قطعی[ویرایش]

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

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

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

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

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

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

از آن به بعد، این روش در جاهای مختلفی و به وسیلهٔ افراد مختلفی، استفاده شد.

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

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

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

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

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

  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. 

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