بلام بلام شاب
From Wikipedia, the free encyclopedia
بلام بلام شاب یک الگوریتم مولد اعداد شبه تصادفی میباشد که در سال ۱۹۸۶ توسط لنور بلام و مانوئل بلام و مایکل شاب ارائه شد.
ساختار این الگوریتم به صورت زیر میباشد :
که در آن "M=p*q" میباشد که p و q اعداد اول بزرگ میباشند. در هر مرحله از این الگوریتم مقدار خروجی در xn+1 قرار گرفته میشود. و نتیجه این مولد میتواند از بیت همزادی زوج یا فرد یا بیتهای کم ارزش این عدد به دست بیاید. یعنی همانطور که در مثال خواهید دید به ازای هر بیت یک عدد که قصد ساخت آن را داریم یک بار این رابطه را اجرا کنیم و با استفاده از عدد به دست آمده بیت مورد نظر را دریافت کنیم. عدد x0 که نیز به عنوان نقطه شروع برای این الگوریتم باید قرار داده شود باید نسبت به M اول باشد. همچنین ۱ نمیتواند به عنوان نقطه شروع در نظر گرفته شود. همچنین باید بزرگ ترین مقسوم علیه مشترک نتیجه تابع اویلر بر دو عدد p , q عددی کوچک شود. هر دو عدد p , q باید با عدد ۳ بهپیمانه ۴متجانس باشند.
یکی از جذابیتهای الگوریتم بلام بلام شام این است که عدد xi را میتوان بهطور مستقیم با استفاده از قضیه اویلر به دست آورد.
که در آن یک تابع کارمیکال میباشد.
).