تولید اعداد شبه تصادفی مبتنی بر اتوماتای سلولی و مورچه های لانگتون

محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسی

سید مرتضی حسینی ¹ (دانشگاه ازاد مشهد)
حسین کریمی ² (دانشگاه آزاد اسلامی، واحد مشهد، گروه کامپیوتر نرم افزار، مشهد، ایران)
مجید وفایی جهان ³ (دانشگاه آزاد اسلامی، واحد مشهد، گروه کامپیوتر نرم افزار، مشهد، ایران)

تاریخ دریافت : 1396/03/30 تاریخ پذیرش : 1396/03/30 تاریخ انتشار : 1393/06/01

کلید واژه: cellular automata, تست, اتوماتای سلولی, .Diehard مولد اعداد شبه تصادفی, مورچه لانگتون, آزمون آنتروپی, Pseudo-Random Number Generator, Langton's Ant, Entropy Test, Diehard Test,

چکیده مقاله :

رفتار تکاملی و پیچیده اتوماتای سلولی باعث کاربرد آن در تولید اعداد شبه تصادفی، رمزنگاری اطلاعات و حل مسائلبهینه سازی شده است. در تولید اعداد شبه تصادفی، این ساختارتوانایی تولید دنباله نامحدود و طولانی ندارد و این باعث شده استکه برای افزایش دنباله اعداد از اتوماتای سلولی غیرهمگن(با قوانین متغیر ) و یا از عامل های تحریک کننده اتوماتای سلولی باترکیب چند اتوماتا استفاده شود. در این مقاله از اتوماتای سلولی ترکیبی غیرهمگن با کمک مورچه های لانگتون، برای تولید اعدادشبه تصادفی استفاده شده است. مورچههای لانگتون یک سیستم دینامیکی گسسته می باشند که دارای رفتاری بسیار پیچیدههستند.اتوماتای سلولی به عنوان مولد اعدد شبه تصادفی و مورچه لانگتون به عنوان محرک اتوماتای سلولی و انتخاب کننده قانوناتوماتا است.نتایج به دست آمده نشان می دهد که در ای ن روش، برخلاف انتظار، مورچه های لانگتون و اتوماتای سلولی رفتارآشوب گونه ندارند و رفتاری شبه تصادفی از خود نشان می دهند که در نتیجه باعث به وجود آمدن دنباله ای بسیار طولانی با تعداد2 می توان دست یافت. در این راستا آزمونهای مولد اعداد 􀬷􀯡 سلول به دنباله ای با طول n محدودی سلول می شود؛ به طوری که باو آزمونهای دیگر نشان دهند ة موفقیت این مولد در NIST و Diehard شبه تصادفی انجام شده همچون آزمون آنتروپی، آزمونایجاد دنباله شبه تصادفی است.

چکیده انگلیسی:

Cellular automata with evolutionary and complex behaviors are used in several applications such asgenerating random numbers, cryptography and optimization problems solving. In random numbersgeneration, this structure cannot produce long sequence of random numbers. For increasing thesequence of numbers, heterogeneous cellular automata with variable rules or combination of severalautomata may be used. In this paper combined heterogeneous cellular automata with contribution oflangton's ant as random number generator is presented. Langton's ant is a simple discrete dynamicalsystem, with a surprisingly complex behavior.Cellular automata are considered as generator of randomnumber and langton's ant is considered as stimuli of cellular automata and determiner of automata rule.Experimental results show that, in spite of our expectation, combination of langton's ant and cellularautomata does not have chaos behavior but illustrates pseudo-random behaviorwhich it results incycles of very long period lengths with limited number of cells such that a period length 2􀬷􀯡 isobtained by n cells. In addition to independence of initial core (initial value), it has been also provedthat generated numbers are independent of each other. Accordingly, some tests of random numbergenerators such as entropy, overlapping, minimum distance and Diehard(set of 17 triple test) havebeen performed and all of them have been successfully passed