Pseudorandom sequence generation using binary cellular automata

Abstract

Rasgele sayılar simülasyonlardan sans oyunlarına, güvenlik protokollerinden uygulamalımatematik ve fizik alanlarına kadar bir çok uygulamanın isleyisinde yer alan temel unsurlardanbiridir. Rasgele sayıların bilimsel ve teknolojik amaçlı kullanım alanı genisledikçehızlı ve ekonomik üretim yöntemleri de arastırmacılar için ilgi konusu olmaktadır.Cellular Automata (CA), basit yapısının yanında tabiattaki kamasık yapılı olayları modellemeyeuygunluguyla ön plana çıkmıs bir çesit ayrık fonksiyonlar grubudur. Rasgeledizi üretmeye olan elverisliligini ve yaygın olarak kullanılan rasgele sayı üreteçlerine üstüngelen yönlerini açıklayan bir çok çalısma halihazırda literatürde yer almaktadır.CA alanında ekseriyetle 3 girdi alan tek boyutlu fonksiyonlar üzerine arastırmalar bulunuyor.Biz bu çalısmada, 5 girdi alan CA fonksiyonları üzerinde bir tarama yaparakrasgele sayı üretme kabiliyeti yüksek olan fonksiyonları belirlemeyi hedefledik. Ölçüolarak NIST tarafından hazırlanan istatistiksel test grubu sonuçlarını baz aldık.5 girdi alan CA fonksiyonları kümesi 4,2 milyardan fazla fonksiyon içeren çok genis birküme. Dolayısıyla fonksiyonları teste tabi tutmadan evvel iyi sonuç vermeyecegi tahminedilen fonksiyonların elenmesi gerekiyor.Literatürde, bu tarz bir eleme söz konusu oldugunda entropi degerlerinin baz alındıgınıgörürüz. Fakat biz bu çalısmada karsılıklı bilgiyi (mutual information) esas aldık. Budegisiklige gitmekteki asıl amaç, entropi gibi üretilmis sayı dizisi üzerinde hesaplanan birölçü yerine dogrudan fonksiyon üzerinde hesaplanan pratik bir ölçünün kullanılabilirliginiarastırmaktı. 3 ve 4 girdi alan fonksiyonlardan edinilen verilere göre çok iyi istatistikselnitelikte dizi üreten fonksiyonların tamamının karsılıklı bilgi degerinin sıfır oldugugörülüyor. Bu gözlemden yola çıkarak, 5 girdi alan fonksiyonlar üzerinde sıfır karsılıklıbilgiye sahip olmayı bir eleme kriteri olarak kullandık. Bu seçimin sebepleri ve sonuçlarıda çalısmada genis olarak incelendi.Sonuç olarak, 248 milyonun üzerinde fonksiyon teste tabi tutuldu ve test sonuçlarısunuldu. Bunların arasından istisnai nitelikte iyi performans gösteren 120 fonksiyonçalısmanın sonunda belirtildi. Ek olarak, 120 fonksiyon arasından seçilen bir fonksiyonunayrıntılı istatistiksel incelemesine yer verildi.

Random numbers are an integral part of many applications from computer simulations,gaming, security protocols to the practices of applied mathematics and physics. Asrandomness plays more critical roles, cheap and fast generation methods are becoming apoint of interest for both scientific and technological use.Cellular Automata (CA) is a class of functions which attracts attention mostly due to thepotential it holds in modeling complex phenomena in nature along with its discretenessand simplicity. Several studies are available in the literature expressing its potentialityfor generating randomness and presenting its advantages over commonly used randomnumber generators.Most of the researches in the CA field focus on one-dimensional 3-input CA rules. Inthis study, we perform an exhaustive search over the set of 5-input CA to find out therules with high randomness quality. As the measure of quality, the outcomes of NISTStatistical Test Suite are used.Since the set of 5-input CA rules is very large (including more than 4.2 billions of rules),they are eliminated by discarding poor-quality rules before testing.In the literature, generally entropy is used as the elimination criterion, but we preferredmutual information. The main motive behind that choice is to find out a metric forelimination which is directly computed on the truth table of the CA rule instead of thegenerated sequence. As the test results collected on 3- and 4-input CA indicate, all ruleswith very good statistical performance have zero mutual information. By exploiting thisobservation, we limit the set to be tested to the rules with zero mutual information. Thereasons and consequences of this choice are discussed.In total, more than 248 millions of rules are tested. Among them, 120 rules show outstandingperformance with all attempted neighborhood schemes. Along with these tests,one of them is subjected to a more detailed testing and test results are included.