Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Например, в мире с 1996 г. распро­страняется компакт-диск «The Marsaglia random number CDROM» [51],который содержит 4,8 млрд. «истинно случайных» бит, а в сети Интернетможно найти массивы случайных чисел, полученные в результате измере­ния атмосферных шумов (Random.Org, [70]) или регистрации радиоактив­ного распада (HotBits, [36]).Подобные методы, основанные на различных физических процессах иявлениях, имеющих случайную природу, носят название генераторов ис­тинно случайных последовательностей.

Они дают очень хорошие стати­стические результаты, но требуют колоссального времени для получениясколько-нибудь длинной последовательности. Так, быстродействие генера­тора HotBits составляет всего около 100 байт в секунду. После изобретениякомпьютеров начались поиски эффективных программных способов гене­рации случайных чисел.Поскольку любая программа описывает некоторый детерминирован­ный алгоритм, получить истинно случайные числа с ее помощью невоз­можно. Джон фон Нейман по этому поводу отмечал, что «каждый, ктоиспользует арифметические методы генерирования случайных чисел, без* условно, грешит» [79].

Последовательности, полученные при помощи по­добных генераторов, не являются истинно случайными, однако обладаютсхожими (в идеальном случае — неотличимыми) свойствами, а потому но­сят название псевдослучайных.К настоящему времени разработано большое количество всевозмож­ных алгоритмов генерации псевдослучайных последовательностей, осно­ванных на использовании положений теории чисел, свойствах различныхалгебраических систем, применении конечных (в т.

ч. клеточных автома­тов) и т.д. Тем не менее, практически все такие алгоритмы в силу своейдетерминированной природы обладают в той или иной мере различныминедостатками, такими как слишком короткий период выходной последо­вательности, наличие корреляции между различными членами последова­тельности, неравномерное распределение, предсказуемость, недостаточная-11скорость и т.д. Поэтому разработка новых алгоритмов генерации псевдо­случайных последовательностей, сочетающих в себе высокое быстродей­ствие и хорошие статистические свойства формируемой выходной последо­вательности, до сих пор остается актуальной научной и инженерной зада­чей.ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫДиссертационная, работа посвящена разработке новых методов гене­рации псевдослучайных равномерно распределенных двоичных последова­тельностей, основанных на использовании клеточных автоматов.

К основ­ным достоинствам разработанных методов относятся контролируемый-пе­риод и хорошие статистические свойства псевдослучайных последователь­ностей, эффективность и высокое быстродействие аппаратной реализациигенераторов.Актуальность проблемы. Актуальность обусловлена широким приме­нением псевдослучайных последовательностей в имитационном моделиро­вании, методах Монте-Карло, криптографии, программировании и иныхобластях. Свой вклад в исследование псевдослучайных последовательно­стей и их генераторов внесли такие известные ученые, как А. Н. Колмого­ров, Р. фон Мизес, Дж. фон Нейман, Дж. Марсалья, Д. Кнут, П.

Лекваер,С. Вольфрам и др. Вопросы генерации псевдослучайных последовательно­стей широко обсуждаются на отечественных и зарубежных научных кон­ференциях, таких как MCQMC, The Winter Simulation Conference, Crypto,EuroCrypt, FSE, CHES, Sibecrypt, РусКрипто и т.д.По мере развития возможностей вычислительной техники разрывмежду предъявляемыми требованиями и возможностями существующихгенераторов неуклонно возрастает. Как показал проведенный в рамках дис­сертационного исследования обзор, основными проблемами при разработ­ке генераторов псевдослучайных последовательностей являются сочетаниевысокого быстродействия, эффективности реализации и хороших статисти­ческих свойств.Одним из перспективных направлений является разработка новых ме­тодов генерации псевдослучайных последовательностей, рассчитанных на-12реализацию на параллельных вычислительных устройствах, что связано сосменой парадигмы вычислительного процесса и переходом от последова­тельных вычислений к параллельным.

При этом задача генерации случай­ной последовательности с заданным законом распределения может бытьсведена к задаче генерации случайной равномерно распределенной двоич­ной последовательности.Цель и задачи. Целью исследований являлась разработка новых гене­раторов псевдослучайных равномерно распределенных двоичных последо­вательностей, отвечающих следующим требованиям:- выходные последовательности генераторов на длине периода должныбыть статистически неотличимы от случайных равномерно распреде­ленных двоичных последовательностей, что должно подтверждатьсяуспешным прохождением соответствующих специализированных те­стов;- период выходных последовательностей генераторов должен превосхо­дить требуемые на практике значения;- быстродействие и эффективность реализации генераторов на парал­лельных вычислительных устройствах, таких как ПЛИС, должныбыть не ниже, чем у известных аналогов.При этом исследования были изначально ограничены рассмотрением гене­раторов, основанных на использовании клеточных автоматов.Для достижения поставленной цели были решены следующие задачи:- проведен обзор наиболее распространенных генераторов псевдослу­чайных последовательностей, выявлены их основные достоинства инедостатки, рассмотрены методы улучшения статистических свойстввыходных последовательностей;- исследованы свойства клеточных автоматов;- осуществлен синтез структуры и обоснован выбор параметров гене­раторов псевдослучайных последовательностей на основе клеточныхавтоматов;- экспериментально исследованы статистические свойства выходных по­следовательностей разработанных генераторов и подтверждено их со­ответствие предъявленным требованиям;-13- разработана аппаратная реализация предложенных генераторов псев­дослучайных последовательностей и продемонстрировано ее превос­ходство над существующими аналогами как по быстродействию, так ипо эффективности.Предмет и объект исследований.

Предметом исследований являютсяметоды генерации псевдослучайных последовательностей, а объектом — ге­нераторы псевдослучайных двоичных последовательностей с равномернымраспределением, основанные на использовании клеточных автоматов.Методы исследований. Теоретические методы исследований включалиприменение теории конечных автоматов, теории графов, теории вероятно­сти; эмпирические — проведение компьютерного моделирования и приме­нение методов математической статистики для оценки свойств двоичныхпоследовательностей.

Для программной реализации был использован языкС # и платформа Microsoft .NET; разработка аппаратной реализации осу­ществлялась на языке описания цифровых схем VHDL, в качестве аппа­ратной) платформы применялась ПЛИС Altera Cyclone П.Достоверность полученных результатов. Достоверность теоретическихрезультатов обеспечивается строгим математическим обоснованием утвер­ждений и подкрепляется их согласованностью с данными компьютерно­го моделирования. Достоверность эмпирических результатов достигаетсяза счет применения стандартных общепринятых инструментов статистиче­ского анализа. Корректность аппаратной реализации подтверждается со­ответствием ее выходных последовательностей и последовательностей, по­лученных при помощи программной реализации.Научная новизна.

Научная новизна работы заключается в следующем:- исследовано влияние веса локальной функции связи на распределениезначений ячеек памяти клеточных автоматов; сформулирован, дока­зан и подтвержден экспериментально критерий сохранения равномер­ности распределения;- впервые сформулировано понятие лавинного эффекта для клеточныхавтоматов; получено теоретическое описание характеристик оптималь­ного лавинного эффекта и эмпирические зависимости характеристиклавинного эффекта от выбора окрестностей ячеек; показано, что кле--14точные автоматы обладают свойством размножения изменений;- впервые введено и исследовано понятие пространственного периода вклассических клеточных автоматах; сформулировано и доказано необ­ходимое условие существования пространственного периода; показано,что нетривиальный пространственный период существенно снижаетверхнюю границу периода последовательности внутренних состояний;- разработаны новые методы генерации псевдослучайных последова­тельностей; на основании свойств клеточных автоматов осуществленсинтез структуры генератора и обоснован выбор его параметров; эмпи­рически подтверждено соответствие статистических свойств выходныхпоследовательностей современным требованиям.Большинство теоретических результатов получено для общего случаяn-мериых классических клеточных автоматов с произвольным радиусомлокальности и неоднородных клеточных автоматов с произвольной мощ­ностью окрестности; для важного класса двумерных булевых клеточныхавтоматов также получены частные результаты.Практические результаты.

Характеристики

Список файлов диссертации