نمایش مبدأ برای بلام بلام شاب

'''بلام بلام شاب''' یک [[الگوریتم]] [[مولد اعداد شبه تصادفی]] می‌باشد که در سال ۱۹۸۶ توسط [[لنور بلام]] و [[مانوئل بلام]] و [[مایکل شاب]] ارائه شد.

ساختار این الگوریتم به صورت زیر می‌باشد :

{{چپ‌چین}}
:<math>x_{n+1} = x_n^2 \bmod M</math>
{{پایان چپ‌چین}}

که در آن "M=p*q" می‌باشد که p و q [[اعداد اول]] بزرگ می‌باشند. در هر مرحله از این الگوریتم مقدار خروجی در ''x''<sub>''n''+1</sub> قرار گرفته می‌شود. و نتیجه این مولد می‌تواند از [[بیت همزادی]] زوج یا فرد یا [[بیت (رایانه)|بیت]]‌های کم ارزش این عدد به دست بیاید. یعنی همانطور که در مثال خواهید دید به ازای هر بیت یک عدد که قصد ساخت آن را داریم یک بار این رابطه را اجرا کنیم و با استفاده از عدد به دست آمده بیت مورد نظر را دریافت کنیم.
عدد ''x''<sub>0</sub> که نیز به عنوان نقطه شروع برای این الگوریتم باید قرار داده شود باید نسبت به M اول باشد. همچنین ۱ نمی‌تواند به عنوان نقطه شروع در نظر گرفته شود. همچنین باید [[بزرگ ترین مقسوم علیه مشترک]] نتیجه [[تابع اویلر]] بر دو عدد p , q عددی کوچک شود.
هر دو عدد p , q باید با عدد ۳ به[[پیمانه]] ۴[[متجانس]] باشند.

یکی از جذابیت‌های الگوریتم بلام بلام شام این است که عدد ''x''<sub>i</sub> را می‌توان به‌طور مستقیم با استفاده از [[قضیه اویلر]] به دست آورد.
{{چپ‌چین}}

:<math>x_i = \left( x_0^{2^i \bmod \lambda(M)} \right) \bmod M</math>
{{پایان چپ‌چین}}

که در آن <math>\lambda</math> یک [[تابع کارمیکال]] می‌باشد.
{{چپ‌چین}}
<math>\lambda(M) = \lambda(p\cdot q) = \operatorname{lcm}(p-1, q-1)</math>).
{{پایان چپ‌چین}}

== امنیت ==
این روش برای [[تولید اعداد تصادفی]] برای مصارف [[شبیه سازی]] مناسب نمی‌باشد و تنها برای مصارف [[رمزنگاری]] مناسب می‌باشد. زیرا این الگوریتم بسیار کند می‌باشد.

از آنجایی که [[پیچیدگی محاسباتی]] الگوریتم‌های [[تجزیه]] و شکستن آن‌ها به عوامل اول بالاست این الگوریتم از لحاظ امنیتی دارای رتبه بالایی می‌باشد. برای پیش‌بینی بیت‌های عددی که با استفاده از این الگوریتم به دست می آید باید محاسباتی با پیچیدگی معادل تجزیه عدد M به عوامل اول را انجام داد.

از آنجایی که با رشد M پیچیدگی محاسباتی افزایش میابد می‌توان نتیجه گرفت که برای مقادیر بزرگ M نمیتوان روشی غیر تصادفی که اعدادی معادل خروجی این الگوریتم به ما بدهد یافت. این روش امنیتی در امنیت روش‌های رمز نگاری دیگر مانند [[رمز نگاری آر اس ای]] را دارا می‌باشد.
== مثال ==
{{چپ‌چین}}
<math>p=11</math>، <math>q=19</math>
<math>s=3</math>
{{پایان چپ‌چین}}
برای شروع هسته انجام عملیات را برابر ۳ قرار میدهیم که x0 در مرحله اول از همین هسته تولید خواهد شد.

میتوانیم انتظار سیکل تولید اعداد تصادفی طولانی را با همین اعداد p , q کوچک داشته باشیم زیرا :
{{چپ‌چین}}

<math>{\rm gcd}(\varphi(p-1), \varphi(q-1))=2</math>.

<math>x_1</math>، <math>x_2</math>، <math>\ldots</math> <math>x_5</math> = 9, 81, 82, 36, 42, 92

{| class="wikitable"
|-
! Even parity bit
! Odd parity bit
! [[Least significant bit]]
|-
| 0 1 1 0 1 0
| 1 0 0 1 0 1
| 1 1 0 0 0 0
|}
{{پایان چپ‌چین}}
== منابع ==
{{پانویس}}
بلام بلام شاب ([//en.wikipedia.org/w/index.php?title=Blum_Blum_Shub&oldid=462369865])
* Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", ''SIAM Journal on Computing'', volume 15, pages 364&ndash;383, May 1986.
* Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", ''Advances in Cryptology: Proceedings of Crypto '82''. Available as [ftp://ftp.hacktic.nl/pub/mirrors/Advances%20in%20Cryptology/HTML/PDF/C82/61.PDF PDF]{{پیوند مرده|date=اکتبر ۲۰۱۹ |bot=InternetArchiveBot }}.
* Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. Available as [https://web.archive.org/web/20110719120754/http://daimi.au.dk/~mg/mamian/random-bits.pdf PDF] and [https://web.archive.org/web/20110719120806/http://daimi.au.dk/~mg/mamian/random-bits.ps.gz Gzipped Postscript].
== پیوند به بیرون ==
* [https://web.archive.org/web/20090524070627/http://firefly.is-a-geek.org/gmpbbs/ GMPBBS] (archived 2009-05-24 at the [[ماشین برگشت به گذشته]]), a [[پروانه عمومی همگانی گنو|GPL]]'ed [[GNU Multi-Precision Library|GMP]]-based implementation of Blum Blum Shub by Mark Rossmiller. Retrieved 2011-09-05.
* [http://code.google.com/p/javarng/ An implementation in Java] (Note: this is not a correct implementation because it does not enforce ''p'' and ''q'' as being prime; it just enforces ''p'' congruent to 3 (mod 4).)
* [http://www.ciphersbyritter.com/NEWS2/TESTSBBS.HTM Randomness tests]

[[رده:الگوریتم‌ها]]
[[رده:مولدهای امن اعداد شبه‌تصادفی در رمزنگاری]]
[[رده:مولدهای عدد شبه‌تصادفی]]