چگونه اعداد تصادفی واقعا تصادفی بسازیم!

۱۳۹۶-۰۲-۱۸

6 دقیقه

ساخت اعداد تصادفی

شاید برای شما هم پیش آمده باشد که برای ساخت یک بازی یا الگوریتم رمزگذاری یا هر منظور دیگری نیاز به ساخت اعداد تصادفی داشته باشید! ممکن است فکر کنید که ساخت یک عدد تصادفی کار زیاد پیچیده‌ای نیست و با صدازدن یک تابع Rand یا تابعی مشابه آن، کار تمام می‌شود. اما عدد تولیدشده با این روش چقدر تصادفی است؟ آیا نتیجه قابل تکرار نیست؟

در این مقاله قصد داریم این موضوع را مورد کنکاش قرار دهیم. پس با سیسوگ همراه شوید.

چرا نمی توان اعداد تصادفی را واقعا تصادفی نامید؟

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

برای روشن‌تر شدن مسئله فوق به مثال زیر توجه کنید:

int main(void)
{
	int i = 0;
	for(i=0;i<10;i++)
		printf("%i\t",rand());
}

int main(void)

{

int i = 0;

for(i=0;i<10;i++)

printf("%i\t",rand());

}

در برنامه فوق ما قصد داشتیم که 10 عدد تصادفی ایجاد کنیم و نتیجه را نمایش دهیم. برای این کار از یک حلقه استفاده می‌کنیم که 10 بار تابع rand را فراخوانی کند و نتیجه را نمایش دهد. به نظر توالی اعداد تولیدشده اتفاقی هستند.

البته در نظر داشته باشید این توالی تا وقتی اتفاقی است که ما از الگوریتم تولید آنها اطلاع نداشته باشیم. وقتی الگوریتم را مطالعه کنیم و روش عملکرد آن را دربیابیم با داشتن یکی از اعداد می‌توانیم عدد بعدی و حتی قبلی را حدس بزنیم! در این مرحله این مسئله را نادیده می‌گیریم.

41	18467	6334	26500	19169	15724	11478	29358	26962	24464

1	41 18467 6334 26500 19169 15724 11478 29358 26962 24464

انتظار داریم که با هر بار اجرای برنامه ده عدد کاملاً اتفاقی داشته باشیم؛ اما هر بار که برنامه را اجرا می‌کنیم، همین ده عدد نمایش داده می‌شوند. (ممکن است برای شما ده عدد دیگر باشد ولی نتیجه تکرارپذیر است.) یعنی اعداد واقعاً تصادفی نیستند و توسط الگوریتمی ایجاده شده‌اند که هیچ پارامتر متغیری نداشته است.

برای رفع این نقص، تابعی وجود دارد به نام srand که با دریافت یک عدد، اعداد تصادفی را از آن نقطه شروع خواهد کرد. به این معنی که اگر در هر بار اجرای برنامه، ما یک عدد تصادفی (که خود ساخت این عدد نیز مسئله‌ساز است.) به این تابع بدهیم، خروجی نیز اعداد تصادفی است!

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

int main(void)
{
	int i = 0;
	srand ( time(NULL) );
	for(i=0;i<10;i++)
		printf("%i\t",rand());
	return 0;
}

int main(void)

{

int i = 0;

srand ( time(NULL) );

for(i=0;i<10;i++)

printf("%i\t",rand());

return 0;

}

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

فرض کنید ما سیستم تولید رمز عبور تصادفی را با این روش پایه‌گذاری کرده‌ایم؛ یک هکر با دانستن زمان ایجاد رمزها، اگر زمان سیستم خود را به گذشته تغییر دهد (یعنی دقیقاً همان زمانی که ما رمز عبورها را ایجاد کرده‌ایم) خواهد توانست رمزهای مشابه ایجاد کند و حتی با دست‌کاری زمان سیستم، رمزهایی که در آینده ایجاد می‌کنیم را نیز حدس بزند.

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

چرا در سیستم‌های میکروکنترلری وضع حاد‌تر است؟

معمولاً در سیستم‌های مبتنی بر میکروکنترلر، زمان واقعی (RTC) وجود ندارد و زمان سیستم معمولاً از زمان روشن شدن دستگاه سنجیده می‌شود. خود این مسئله باعث می‌شود که عملاً تابع srand بی‌استفاده شود؛ چراکه مثلاً همیشه در زمان خاصی از اجرای برنامه فراخوانی می‌شود و همیشه یک مقدار خاص به آن داده می‌شود. برای روشن شدن مسئله، برنامه بالا را برای سخت‌افزار آردوینو بازنویسی می‌کنیم.

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);
  srand(millis());

  for(int i=0;i<10;i++)
    Serial.println(rand());
}

void loop() {
  // put your main code here, to run repeatedly:

}

void setup() {

// put your setup code here, to run once:

Serial.begin(9600);

srand(millis());

for(int i=0;i<10;i++)

Serial.println(rand());

}

void loop() {

// put your main code here, to run repeatedly:

}

همان‌طور که مشاهده می‌کنید با هر بار اجرای برنامه (ریست کردن یا خاموش و روشن کردن) برنامه خروجی یکسانی را نمایش می‌دهد. البته لازم به ذکر است که اگر در سیستم از RTC استفاده شود، مقداری وضع بهبود پیدا می‌کند و حدس زدن خروجی سخت‌تر خواهد شد. اما باز به معنی واقعیِ کلمه، اعداد تولیدشده تصادفی نخواهند بود.

چراکه برای تصادفی بودن یک دنباله از اعداد، باید دو شرط وجود داشته باشد؛ اول: دنباله تکرارپذیر نباشد و دوم: اعداد تولیدشده قابل حدس زدن نباشند.

راه‌حل تولید اعداد تصادفی واقعی چیست؟

ااما راه‌حل اساسی برای تولید اعداد واقعاً تصادفی چیست؟

همان‌طور که گفته شد اعداد تصادفی وقتی به مفهوم واقعی خود نزدیک‌تر می‌شوند که غیرقابل‌پیش‌بینی و تکرارناپذیر باشند. اگر پایه تولید اعداد تصادفی را میزان تجمع نوع خاصی از باکتری بر روی یک سطح انتخاب کنیم، اعداد تولیدشده با این روش به‌راحتی قابل پیش‌بینی نیستند؛ چراکه عوامل متغیر زیادی در میزان رشد آن نوع خاص از باکتری وجود خواهد داشت. به‌عنوان‌مثال: دمای هوا، میزان نور، میزان رطوبت، میزان وجود نوع دیگری از باکتری و… . به همین دلیل حدس این‌که در یک زمان خاص چه مقدار باکتری بر روی سطح موردنظر ما تجمع کرده است عملاً امری غیرممکن خواهد بود و می‌توان تا حدود زیادی گفت که عدد به‌دست‌آمده عددی است تصادفی! نمونه فوق فقط یک مثال برای نشان دادن این مسئله بود که با زیاد کردن پارامترهای دخیل در تولید یک عدد تصادفی، می‌توان به همان نسبت حدس زدن عدد تولیدشده را دشوارتر کرد.

روش‌های متفاوتی برای تولید اعداد تصادفی با استفاده از اصول ذکرشده وجود دارد. اما روش‌هایی که چندان پیچیده نباشند و بتوان به‌راحتی آن‌ها را پیاده‌سازی کرد محدود هستند. ما در این مقاله قصد داریم تا برای تولید اعداد تصادفی از نویز سفید (White Noise) استفاده کنیم. از نظر فیزیکدانان نویز سفید سیگنالی تصادفی است که تراکم طیفی ثابتی دارد.
اگر بخواهیم به شکل ساده‌تر مسئله را بیان کنیم باید بگوییم که مثلاً گوش ما انسان‌ها، معمولاً محدوده‌ی فرکانس ۲۰ هرتز تا ۲۰ هزار هرتز را می‌شنود. اگر یک دستگاه صوتی بخواهد نویز سفید برای گوش ما تولید کند، باید توان امواجی که از آن در محدوده فرکانسی ۲۰ تا ۴۰ هرتز ساطع می‌شود، با توان امواجی که مثلاً در محدوده فرکانسی ۱۰۰۰۰ و ۱۰۰۲۰ ساطع می‌شود، برابر باشد.

صدای نویز سفید را بشنوید:

صدای اقیانوس نیز نویز سفید است:

چگونه نویز سفید بسازیم؟

یکی از ساده‌ترین روش‌های تولید نویز سفید، استفاده از دیود به‌صورت بایاس معکوس هست. همان‌طور که می‌دانید دیود از پیوند N و P تشکیل شده است. وقتی‌که دیود را به‌صورت معکوس در مدار قرار می‌دهیم، پیوند PN گسترش می‌یابد و میزان جریان کمی برقرار می‌شود که به این جریان، جریان نشتی می‌گویند. این جریان با توجه به ماهیت دیود و پیوند PN دارای نویز سفید است.

بر همین اساس برای تولید نویز سفید می‌توان از مدار زیر استفاده کرد:

اگر خروجی مدار فوق را به یک تقویت‌کننده صوتی وصل کنیم، صدای نویز سفید را خواهیم شنید. برای تقویت دامنه و تصحیح امپدانس مدار می‌توان خروجی مدار را به یک تقویت‌کننده عملیاتی (Opamp) وصل کرد.

مدار نهایی به شکل زیر خواهد بود:

چگونه می‌توانم از ژنراتور نویز سفید استفاده کنم؟

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

در برنامه زیر برای ایجاد یک عدد تصادفی از نویز سفید و ADC به کمک توابع Rand و Srand استفاده شده است.

int adc_pin = 0;

void setup(){

  Serial.begin(9600); 
}

void loop()
{
  
  int adc_value = analogRead(adc_pin);
  srand(adc_value);
  Serial.println(rand());
  delay(1000);
}

int adc_pin = 0;

void setup(){

Serial.begin(9600);

}

void loop()

{

int adc_value = analogRead(adc_pin);

srand(adc_value);

Serial.println(rand());

delay(1000);

}

بررسی نتایج

خروجیِ دیجیتالِ مدارِ رندم ژنراتور را برای مدت 15 ساعت با نرخ نمونه‌برداری 500 میکروثانیه ذخیره و موردبررسی قراردادیم که نتایج زیر به‌دست آمد:

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

نمودار پراکندگی داده‌های موجود:

882000 نمونه اول را به صورت فایل صوتی بشنوید:

اطلاعات

لینک و اشتراک

چگونه اعداد تصادفی واقعا تصادفی بسازیم!

ساخت اعداد تصادفی

چرا نمی توان اعداد تصادفی را واقعا تصادفی نامید؟

چرا در سیستم‌های میکروکنترلری وضع حاد‌تر است؟

راه‌حل تولید اعداد تصادفی واقعی چیست؟

چگونه نویز سفید بسازیم؟

چگونه می‌توانم از ژنراتور نویز سفید استفاده کنم؟

بررسی نتایج

شاید برای شما مفید باشد

برد آموزشی و متن باز...

آموزش تصویری نصب سیستم عامل...

دیود چیست؟ نحوه عملکرد دیود...

Zeus ‌

پالت | بازار خرید و فروش قطعات الکترونیک

آیسی | موتور جستجوی قطعات الکترونیک

فروشگاه سیسوگ

سیسوگ فروم | محلی برای پاسخ پرسش‌های شما

نویسنده شو !

نویسنده شو !

پالت | بازار خرید و فروش قطعات الکترونیک

آیسی | موتور جستجوی قطعات الکترونیک

فروشگاه سیسوگ

سیسوگ فروم | محلی برای پاسخ پرسش‌های شما

دیدگاه ها

m4m گفت :

Zeus ‌ گفت :

یه کسی گفت :

زئوس Zeus گفت :

امیرسینا گفت :

زئوس Zeus گفت :

حسین گفت :

زئوس Zeus گفت :

حسین گفت :

شمس الدینی گفت :

زئوس Zeus گفت :

حسین گفت :

زئوس Zeus گفت :

حسین گفت :

زئوس Zeus گفت :

حسین گفت :

زئوس Zeus گفت :

حسین گفت :

زئوس Zeus گفت :

mohammad79h گفت :

زئوس Zeus گفت :

mohammad گفت :

زئوس Zeus گفت :

مصطفی گفت :

زئوس Zeus گفت :

کیان گفت :

زئوس Zeus گفت :

سجاد گفت :

زئوس Zeus گفت :

امید گفت :

زئوس Zeus گفت :

مرتضی گفت :

زئوس Zeus گفت :

مهرداد گفت :

امید گفت :

زئوس Zeus گفت :

زئوس Zeus گفت :

Alaa گفت :

زئوس Zeus گفت :

علی گفت :

زئوس Zeus گفت :

نویسنده شو !

نویسنده شو !

آموزش ها

منو و لینک‌ها

شبکه‌های اجتماعی