Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов
Рассмотрен класс комбинационных генераторов, в котором в качестве комбинирующей функции используется операция суммирования в некотором конечном поле. Исследованы статистические свойства последовательности чисел на выходе комбинационного генератора, где в качестве исходных первичных генераторов испол...
Saved in:
| Date: | 2015 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2015
|
| Series: | Системні дослідження та інформаційні технології |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/116052 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов / А.А. Лавданский, Э.В. Фауре // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 39-50 . — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-116052 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1160522025-02-09T22:30:30Z Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов Оцінка статистичних властивостей послідовностей на виході комбінаційного гене-ратора за допомогою графічних тестів Evaluation of statistical properties of the output sequence of combination generators with graphics tests Лавданский, А.А. Фауре, Э.В. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Рассмотрен класс комбинационных генераторов, в котором в качестве комбинирующей функции используется операция суммирования в некотором конечном поле. Исследованы статистические свойства последовательности чисел на выходе комбинационного генератора, где в качестве исходных первичных генераторов использованы таблицы перестановок с взаимно простыми периодами повторения. Рассмотрены графические методы определения статистических свойств последовательностей чисел. Произведен анализ полученных с помощью графических тестов статистических характеристик последовательности на выходе комбинационного генератора с различным заполнением исходных таблиц перестановок (линейный конгруэнтный метод, квантовый генератор случайных чисел), выполнено их сравнение с характеристиками последовательностей на выходе существующих генераторов случайных (оцифрованные радиошумы) и псевдослучайных («Вихрь Мерсенна») чисел. Полученные результаты свидетельствуют об идентичности полученных с помощью графических методов оценки статистических свойств всех исследуемых последовательностей. Розглянуто клас комбінаційних генераторів, в якому в якості комбінуючої функції використовується операція підсумовування в деякому кінцевому полі. Досліджено статистичні властивості послідовності чисел на виході комбінаційного генератора, де в якості вихідних первинних генераторів використані таблиці перестановок із взаємно простими періодами повторення. Розглянуто графічні методи визначення статистичних властивостей послідовностей чисел. Зроблено аналіз отриманих за допомогою графічних тестів статистичних характеристик послідовності на виході комбінаційного генератора з різним заповненням вихідних таблиць перестановок (лінійний конгруентний метод, квантовий генератор випадкових чисел), виконано їх порівняння з характеристиками послідовностей на виході існуючих генераторів випадкових (оцифровані радіошуми) і псевдовипадкових ("Вихор Мерсена") чисел. Отримані результати свідчать про ідентичність отриманих за допомогою графічних методів оцінки статистичних властивостей всіх досліджуваних послідовностей. In this paper, we consider a class of combination generators wherein the summation operation in a finite field (sum modulo) is used as the combining function. The statistical properties of sequences of numbers at the output of the combination generator where the primary source generators use permutation tables with relatively prime periods of recurrence is studied. Graphical methods for determining the statistical properties of sequences of numbers are considered. Using graphical tests, the analysis of statistical characteristics of the sequences at the output of the combination generator is performed with different primary tables of permutations (linear congruential method, quantum random number generator) and these characteristics are compared with the characteristics of output sequences of existing generators of random (digitized radio noise) and pseudorandom ("Mersenne twister") numbers. The results demonstrate identical statistical properties of all sequences tested in this pape. 2015 Article Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов / А.А. Лавданский, Э.В. Фауре // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 39-50 . — Бібліогр.: 12 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/116052 621.391:004.73 ru Системні дослідження та інформаційні технології application/pdf Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| spellingShingle |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Лавданский, А.А. Фауре, Э.В. Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов Системні дослідження та інформаційні технології |
| description |
Рассмотрен класс комбинационных генераторов, в котором в качестве комбинирующей функции используется операция суммирования в некотором конечном поле. Исследованы статистические свойства последовательности чисел на выходе комбинационного генератора, где в качестве исходных первичных генераторов использованы таблицы перестановок с взаимно простыми периодами повторения. Рассмотрены графические методы определения статистических свойств последовательностей чисел. Произведен анализ полученных с помощью графических тестов статистических характеристик последовательности на выходе комбинационного генератора с различным заполнением исходных таблиц перестановок (линейный конгруэнтный метод, квантовый генератор случайных чисел), выполнено их сравнение с характеристиками последовательностей на выходе существующих генераторов случайных (оцифрованные радиошумы) и псевдослучайных («Вихрь Мерсенна») чисел. Полученные результаты свидетельствуют об идентичности полученных с помощью графических методов оценки статистических свойств всех исследуемых последовательностей. |
| format |
Article |
| author |
Лавданский, А.А. Фауре, Э.В. |
| author_facet |
Лавданский, А.А. Фауре, Э.В. |
| author_sort |
Лавданский, А.А. |
| title |
Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов |
| title_short |
Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов |
| title_full |
Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов |
| title_fullStr |
Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов |
| title_full_unstemmed |
Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов |
| title_sort |
оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| publishDate |
2015 |
| topic_facet |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/116052 |
| citation_txt |
Оценка статистических свойств последовательностей на выходе комбинационного генератора с помощью графических тестов / А.А. Лавданский, Э.В. Фауре // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 39-50 . — Бібліогр.: 12 назв. — рос. |
| series |
Системні дослідження та інформаційні технології |
| work_keys_str_mv |
AT lavdanskiiaa ocenkastatističeskihsvoistvposledovatelʹnosteinavyhodekombinacionnogogeneratoraspomoŝʹûgrafičeskihtestov AT faureév ocenkastatističeskihsvoistvposledovatelʹnosteinavyhodekombinacionnogogeneratoraspomoŝʹûgrafičeskihtestov AT lavdanskiiaa ocínkastatističnihvlastivosteiposlídovnosteinavihodíkombínacíinogogeneratorazadopomogoûgrafíčnihtestív AT faureév ocínkastatističnihvlastivosteiposlídovnosteinavihodíkombínacíinogogeneratorazadopomogoûgrafíčnihtestív AT lavdanskiiaa evaluationofstatisticalpropertiesoftheoutputsequenceofcombinationgeneratorswithgraphicstests AT faureév evaluationofstatisticalpropertiesoftheoutputsequenceofcombinationgeneratorswithgraphicstests |
| first_indexed |
2025-12-01T10:43:08Z |
| last_indexed |
2025-12-01T10:43:08Z |
| _version_ |
1850302308879958016 |
| fulltext |
А.А. Лавданский, Э.В. Фауре, 2015
Системні дослідження та інформаційні технології, 2015, № 2 39
УДК 621.391:004.73
ОЦЕНКА СТАТИСТИЧЕСКИХ СВОЙСТВ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ НА ВЫХОДЕ
КОМБИНАЦИОННОГО ГЕНЕРАТОРА
С ПОМОЩЬЮ ГРАФИЧЕСКИХ ТЕСТОВ
А.А. ЛАВДАНСКИЙ, Э.В. ФАУРЕ
Рассмотрен класс комбинационных генераторов, в котором в качестве комби-
нирующей функции используется операция суммирования в некотором конеч-
ном поле. Исследованы статистические свойства последовательности чисел на
выходе комбинационного генератора, где в качестве исходных первичных ге-
нераторов использованы таблицы перестановок с взаимно простыми периода-
ми повторения. Рассмотрены графические методы определения статистиче-
ских свойств последовательностей чисел. Произведен анализ полученных
с помощью графических тестов статистических характеристик последователь-
ности на выходе комбинационного генератора с различным заполнением ис-
ходных таблиц перестановок (линейный конгруэнтный метод, квантовый ге-
нератор случайных чисел), выполнено их сравнение с характеристиками
последовательностей на выходе существующих генераторов случайных
(оцифрованные радиошумы) и псевдослучайных («Вихрь Мерсенна») чисел.
Полученные результаты свидетельствуют об идентичности полученных с по-
мощью графических методов оценки статистических свойств всех исследуе-
мых последовательностей
ВВЕДЕНИЕ
Решение многих практических задач невозможно без использования генера-
торов случайных или псевдослучайных чисел (ПСЧ). Последовательности
и случайных, и ПСЧ широко используются в таких важных задачах как ими-
тационное моделирование, криптография, передача данных и др.
Отметим, что под случайной последовательностью чисел будем пони-
мать последовательность, порожденную процессом, исход которого непред-
сказуем и не может быть повторно воспроизведен. Под псевдослучайной
последовательностью чисел будем понимать последовательность, сформи-
рованную с помощью детерминированного алгоритма и обладающую стати-
стическими свойствами, близкими к статистическим свойствам случайных
последовательностей.
ПОСТАНОВКА ПРОБЛЕМЫ
Качественная последовательность ПСЧ должна соответствовать следующим
требованиям: непредсказуемость, воспроизводимость, равномерное распре-
деление слов последовательности, бесконечный период повторения, отсут-
ствие корреляции между словами (символами) последовательности. Заме-
тим, что достичь бесконечного периода повторения невозможно с помощью
А.А. Лавданский, Э.В. Фауре
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 40
детерминированных алгоритмов, поэтому под бесконечным периодом будем
понимать настолько большой период, полное воспроизведение которого бу-
дет значительно превышать вычислительные возможности аппаратного
обеспечения на текущем этапе развития вычислительной техники.
Всем перечисленным выше требованиям (кроме требования по воспро-
зводимости последовательности) отвечают последовательности, полученные
квантованием естественных случайных физических процессов (например,
«белого шума»). По существу, «белый шум» является идеальным источни-
ком случайных последовательностей чисел. Но использование его в качест-
ве источника случайных чисел для ряда практических задач крайне затруд-
нено или просто невозможно. Так, для решения криптографических задач
требуется обеспечить воспроизводимость случайной последовательности
в силу разнесения во времени (или в пространстве) процессов шифрования
и дешифрования. Отсутствие же методов формирования псевдослучайных
последовательностей чисел, отвечающих всем перечисленным требованиям,
стимулирует непрерывный процесс улучшения существующих и поиска но-
вых принципов и подходов в данной области исследований.
Таким образом, разработка и анализ новых методов и устройств фор-
мирования псевдослучайных последовательностей чисел, обладающих ста-
тистическими свойствами, близкими к статистическим свойствам случай-
ных последовательностей чисел, а также обладающих свойством воспроиз-
водимости, является актуальной проблемой.
ПОСТАНОВКА ЗАДАЧИ
Отдельного внимания среди устройств формирования случайных последо-
вательностей чисел заслуживает класс комбинационных генераторов [1],
реализующих комбинацию нескольких исходных генераторов с помощью
некоторой комбинирующей функции. Комбинационные генераторы позво-
ляют избавиться от таких слабых сторон генераторов, как малый период по-
вторения, корреляция символов последовательности, неудовлетворительные
статистические свойства.
Общим недостатком известных комбинационных генераторов является
недостаточная криптографическая стойкость, связанная с наличием корре-
ляции между выходной последовательностью и последовательностями на
выходе исходных генераторов.
Комбинирование нескольких случайных процессов является актуаль-
ным направлением научных и прикладных исследований, находящих отра-
жение, например, в [2, 3], однако множество вопросов все еще остаются не-
изученными.
Цель работы:
анализ эффективности использования операции суммирования в не-
котором конечном поле в качестве комбинирующей функции комбинацион-
ного генератора;
оценка с помощью графических тестов статистических свойств по-
следовательности на выходе комбинационного генератора и их сравнение со
статистическими свойствами случайной последовательностью чисел.
Оценка статистических свойств последовательностей на выходе …
Системні дослідження та інформаційні технології, 2015, № 2 41
РЕШЕНИЕ ЗАДАЧИ
Комбинационный генератор псевдослучайных чисел реализует операцию
комбинации исходных генераторов. В качестве исходных генераторов в ра-
боте рассматриваются генераторы подстановок или предварительно сфор-
мированные таблицы подстановок. В этом случае в процессе работы комби-
национного генератора исходные значения, подлежащие комбинации,
формируются циклически генераторами подстановок или считываются так-
же циклически из таблиц подстановок. Заметим, что закон распределения
чисел внутри подстановки является равномерным для всех значений из об-
ласти определения случайной величины и обладает нулевой ошибкой вос-
произведения закона распределения. Ошибка воспроизведения определяется
в соответствии с методикой, изложенной в [4].
Таким образом, в состав рассматриваемого комбинационного генерато-
ра входят n таблиц подстановок ,2n а также блок реализации комбина-
ции. В данной работе в качестве комбинирующей функции используется
операция суммирования по некоторому модулю .M Структурная схема ге-
нератора представлена на рис. 1.
В і-й исходной таблице в произвольном порядке без повторов и про-
пусков записаны числа от 0 до Mi ]),1[( ni . Заполнение таблиц может про-
изводиться как случайными данными (например, с использованием источ-
ника случайных чисел), так и с помощью детерминированного алгоритма
(линейного конгруэнтного генератора, генератора М-последовательности
и т.д.). Кроме того, представляется возможным использование различных
алгоритмов заполнения для каждой из исходных таблиц.
Период последовательности Т на выходе комбинационного генератора
определяется мощностями алфавитов исходных генераторов (размерами
таблиц) nMMM ,,, 21 и равен их наименьшему общему кратному (НОК):
).,,,( 21 nMMMHOKT
Для получения максимального периода повторения последовательно-
сти на выходе комбинационного генератора мощности алфавитов исходных
генераторов должны быть взаимно простыми. Тогда период
.
1
n
i
iMT
n n
M
Рис. 1. Структурная схема комбинационного генератора
А.А. Лавданский, Э.В. Фауре
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 42
Рассмотрим принцип функционирования описанного комбинационного
генератора, схема которого изображена на рис. 1.
В i-ю таблицу подстановок загружается случайная последовательность
чисел от 0 до Mi ]),1[( ni без повторов и пропусков.
Для каждой таблицы существует счетчик, указывающий на текущее
значение, считываемое из таблицы. Начальное значение счетчиков равно
нулю. Счетчики всех таблиц работают синхронно. При появлении импульса
на выходе генератора импульсов каждый из счетчиков увеличивает свое
значение на единицу.
Данные с выходов каждого из счетчиков являются адресными для счи-
тывания значений из исходных таблиц подстановок. При этом на выходе
каждой из таблиц появляется значение, соответствующее адресу, на кото-
рый указывает счетчик таблицы. Сформированные n слов одновременно по-
ступают на сумматор по модулю M. Выход сумматора является выходом
устройства формирования псевдослучайной последовательности чисел.
Описанная процедура продолжается циклически до выключения устройства.
Каждый из счетчиков при достижении значения, равного размеру соот-
ветствующей ему таблицы, обнуляется.
Выполним анализ статистических свойств описанного комбинационно-
го генератора. Для этого определим методики оценки ПСЧ.
Исследование свойств выходной последовательности генератора ПСЧ
использует две группы тестов: графические и статистические.
Графические тесты отображают статистические свойства последова-
тельности в графическом виде (графики, гистограммы и т.д.), по виду кото-
рых можно судить о случайности последовательности. Важно отметить, что
результат прохождения такого теста является субъективным, поскольку
графический тест не дает численной оценки. Графические тесты являются
первым этапом исследования последовательности псевдослучайных чисел,
который позволяет сделать вывод, стоит ли работать с алгоритмом генера-
ции, сформировавшим эту последовательность, в дальнейшем, либо же он
требует доработки.
К графическим тестам можно отнести следующие: гистограмма рас-
пределения элементов последовательности; распределение на плоскости;
проверка серий (распределение k-грамм); автокорреляционная функция;
профиль линейной сложности; графический спектральный тест.
Статистические свойства исследуемой последовательности могут быть
описаны вероятностью встречи определенного шаблона бит (байт) в этой
последовательности. Для пояснения возьмем, например, распределение бит
в последовательности. Зная длину последовательности в битах, а также по-
считав количество бит, равных «1» и «0», возможно вычислить вероятность
появления в потоке единицы либо нуля. Для случайной последовательности
эти данные известны априорно (очевидно, что для квантованного «белого
шума» вероятность появления единицы (как и нуля) стремится к 0,5). Пред-
положение о случайности тестируемой последовательности строится на ос-
новании сравнения результатов тестирования с соответствующими резуль-
татами случайной последовательности чисел. Это сравнение и положено
в основу статистических тестов. Результатом работы статистического теста
Оценка статистических свойств последовательностей на выходе …
Системні дослідження та інформаційні технології, 2015, № 2 43
есть число (обычно доверительная вероятность подтверждения гипотезы
о случайности последовательности), по которому можно однозначно судить
о прохождении теста.
Рассмотрим графические тесты подробнее.
Гистограмма распределения элементов последовательности. Дан-
ный тест позволяет оценить соответствие распределения слов заданному
закону распределения. Тест также полезен для выявления часто (редко)
встречающихся, либо отсутствующих слов в последовательности. Построе-
ние гистограммы выполняется следующим образом. Производится подсчет
символов, встречающихся в выборке размером V слов. Посчитанное количе-
ство отображается на графике в точке, соответствующей определенному
символу. Для случайной последовательности (равномерное распределение)
все возможные слова должны быть отображены на графике с примерно оди-
наковым значением, стремящимся к ,/ MV где M — мощность алфавита
слов (количество различных слов в последовательности). Также данный тест
можно интерпретировать как статистический, оценив распределение слов
с помощью критерия хи-квадрат, что, впрочем, и производится в пакетах
статистического тестирования.
Распределение на плоскости. Тест позволяет выявить зависимость
между элементами последовательности. Последовательность слов груп-
пируется парами, которые рассматриваются как координаты на двумер-
ном графике, т.е. если представить последовательность слов как
},,,,,{ 210 Vaaaa где V — размер выборки, то координаты графика можно
представить как kax , ,1 kay .10 Vk Отображение этих точек на
плоскости размером 1212 RR точек (где R — разрядность чисел по-
следовательности), является результатом теста. Для случайной последова-
тельности расположение точек на плоскости будет хаотичным, а при рос-
те выборки плоскость полностью будет заполнена точками. Признаком
неслучайной последовательности является наличие на полученном изобра-
жении «узоров» (явно выраженных вертикальных либо горизонтальных ли-
ний, периодических рисунков и т.д.).
Проверка серий (распределение k-грамм). Последовательность из k
слов (бит), при ,1k называется k-граммой. Количество возможных
k-грамм вычисляется как ,kM где M — мощность алфавита. Для примера,
при 2M количество битовых биграмм равно .422 Это биграммы
.11,10,01,00 Для случайной последовательности количество k-грамм для
одного k должно быть примерно одинаковым и стремиться к значению
,
kMk
V
где V — размер выборки. Тест позволяет оценить равномерность
распределения символов в последовательности на основе k-грамм. Для этого
производится подсчет количества различных k-грамм в последовательности
с последующим отображением результата на гистограмме. Успешным про-
хождением теста является равная высота столбцов на гистограмме. Данный
тест (как и гистограмму распределения элементов последовательности) воз-
можно оценить с помощью критерия -квадрат, что позволит однозначно
А.А. Лавданский, Э.В. Фауре
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 44
судить о прохождении теста. Согласно [1], b-ичная последовательность дли-
ны N случайна, если она k-распределена для всех положительных целых
чисел .log2 Nk
Автокорреляционная функция. Тест предназначен для определения
зависимостей внутри последовательности. Для этого определяется степень
корреляции между сдвинутыми копиями последовательности. Обозначим
бит последовательности как ak, где k — номер бита в последовательности,
,0 Vk V — размер выборки. Произведем нормирование битового пред-
ставления исследуемой последовательности следующим образом:
,11 .10 Значение автокорреляционной функции для сдвига i обозна-
чим как .i Тогда значение корреляции для i-того сдвига равно:
.
1
0
2
1
0
V
k
k
V
k
ikk
i
a
aa
V
Для построения графика автокорреляционной функции рассчитывают-
ся значения i для .0 Vi Результатом выполнения теста будет отобра-
жение точек i на графике. При этом значение 0 всегда должно быть рав-
но единице. Чем ближе к нулю значения i в других точках, тем ближе
исследуемая последовательность к случайной. Наличие пиков на графике
(исключая пик в нулевой точке) свидетельствует про внутреннюю корреля-
цию бит последовательности.
Профиль линейной сложности. Линейной сложностью конечной
двоичной последовательности называется число, равное длине самого ко-
роткого регистра сдвига с линейной обратной связью, который генерирует
последовательность, имеющую в качестве первых n членов значения этой
двоичной последовательности. Последовательность слов рассматривается
как битовая последовательность. Для построения графика линейной слож-
ности берутся первые n бит последовательности, 1n . Для этих n бит
производится расчет значения линейной сложности. Определение значения
линейной сложности производится с помощью алгоритма Берлекэмпа-
Мэсси [5–6]. Линейная сложность для n бит откладывается на графике. Ус-
пешным прохождением теста является малое отклонение полученного гра-
фика от графика 2/)( nnf [7].
Графический спектральный тест. Тест предназначен для определе-
ния равномерности распределения нулей и единиц на основе анализа высо-
ты выбросов преобразования Фурье. Для этого битовая последовательность
нормируется )10,11( , после чего к ней применяется дискретное пре-
образование Фурье. Первая половина полученной последовательности гар-
моник отображается на гистограмме. Для случайной последовательности
чисел число гармоник, значительно превышающих среднюю высоту гармо-
ник на гистограмме, должно стремиться к нулю.
Проведем сравнительное тестирование комбинационного генератора
с помощью описанных выше графических тестов.
Оценка статистических свойств последовательностей на выходе …
Системні дослідження та інформаційні технології, 2015, № 2 45
Для тестирования будем использовать два варианта заполнения исход-
ных таблиц — с помощью линейного конгруэнтного метода и с помощью
квантового генератора случайных чисел [8]. Для удобства тестирования бу-
дем использовать мощность алфавита ,256M что позволяет исследовать
как последовательность слов, так и последовательность бит в выборке (пу-
тем последовательной конкатенации битового представления слов в единый
поток бит). Количество исходных таблиц в комбинационном генераторе ус-
тановим равным 4, определив следующие размеры этих таблиц: 251, 241,
239, 229 слов без повторов и пропусков в каждой таблице соответственно.
Такая комбинация исходных таблиц даст максимальный период (поскольку
размеры таблиц взаимно простые), равный 229239241251T
3310732921 слов. Параметры использованных конгруэнтных генераторов
следующие:
;0,251,67,34 01111 SMCK
;0,241,5,158 02222 SMCK
;0,239,222,24 03333 SMCK
.0,229,47,143 04444 SMCK
В случае отсутствия цикла максимальной длины производится формирова-
ние сверхцикла путем конкатенации циклов генератора до достижения мак-
симального периода, равного iM слов [9].
Для сравнения с другими методами формирования последовательно-
стей псевдослучайных чисел в тестирование также включен генератор
«Вихрь Мерсенна» [10].
С целью сравнения статистических параметров последовательности на
выходе комбинационного генератора с параметрами случайной последова-
тельности чисел анализ также будет произведен для последовательности,
сформированной с помощью оцифрованных радиошумов [11]. Будем назы-
вать эту последовательность случайной последовательностью слов.
Рассмотрим графики огибающей для гистограммы распределения эле-
ментов последовательности (рис. 2). Для тестирования взята выборка разме-
ром в 225 слов.
Как следует из рис. 2, различные варианты заполнения исходных таб-
лиц дают одинаковый результат — обеспечивают равномерное распределе-
ние слов в исследуемой выборке. Распределение слов сравнимо с таковым
для генератора «Вихрь Мерсенна» и случайной последовательности слов.
Проведем оценку полученных результатов с помощью критерия 2
[12] с доверительной вероятностью 0,05. Для 255 степеней свободы крити-
ческое значение 2 равно 293,2478.2
255;05,0 Результаты оценки гисто-
граммы распределения следующие: заполнение исходных таблиц с помо-
щью линейного конгруэнтного метода 229,3256);( 2 заполнение
исходных таблиц с помощью квантового генератора случайных чисел
А.А. Лавданский, Э.В. Фауре
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 46
;235,7351)( 2 генератор «Вихрь Мерсенна» ;281,6868)( 2 случайная
последовательность слов 252,6039).( 2
Все полученные значения 2 меньше критического значения 2
255;05,0 ,
что подтверждает равномерность распределения слов в исследуемых после-
довательностях псевдослучайных чисел.
Результаты теста распределения на плоскости изображены на рис. 3.
Выборка для каждой из исследуемых последовательностей постепенно уве-
личивается и составляет 18161514 2,2,2,2 слов, соответственно.
На полученных изображениях не наблюдается различных «узоров»,
а с ростом выборки плоскость полностью покрываются точками. Результаты
тестирования свидетельствуют о присутствии всех возможных биграмм
и отсутствии закономерности в их распределении для всех исследуемых по-
следовательностей чисел.
Результаты определения профиля линейной сложности приведены на
рис. 4. Для тестирования взяты первые 112 бит каждой из исследуемых по-
следовательностей.
Результаты анализа свидетельствуют о равномерном увеличении ли-
нейной сложности по мере увеличения размера выборки для всех исследуе-
мых в работе последовательностей чисел. Полученные графики имеют ма-
лое отклонение от линии ,2/)( nnf что является свидетельством
успешного прохождения теста.
Рис. 2. График огибающей для гистограммы распределения слов последовательно-
сти: а — комбинационный генератор, заполнение исходных таблиц с помощью
линейного конгруэнтного метода; б — комбинационный генератор, заполнение
исходных таблиц с помощью квантового генератора случайных чисел; в — генера-
тор «Вихрь Мерсенна»; г — случайная последовательность слов
а б
К
ол
ич
ес
тв
о
вх
ож
де
ни
й
сл
ов
Слово Слово
в г
К
ол
ич
ес
тв
о
вх
ож
де
ни
й
сл
ов
Слово Слово
Оценка статистических свойств последовательностей на выходе …
Системні дослідження та інформаційні технології, 2015, № 2 47
Результаты прохождения графического спектрального теста представ-
лены на рис. 5. Для проведения теста взяты первые 92 бит каждой из иссле-
дуемых последовательностей. Средняя длина гармоник для каждой из по-
следовательностей соответствует горизонтальной линии.
На гистограммах, приведенных на рис. 5, б, в, г, не наблюдается гармо-
ник, значительно превышающих среднюю длину. Для варианта заполнения
таблиц комбинационного генератора с помощью линейного конгруэнтного
метода (рис. 5,а), на гистограмме присутствуют пики гармоник, превы-
шающие среднюю длину более чем в три раза, чего не наблюдается для ос-
тальных исследуемых выборок. Такой результат тестирования показывает
незначительное отличие последовательности, сформированной с помощью
Рис. 3. Распределение слов на плоскости: а — комбинационный генератор, запол-
нение исходных таблиц с помощью линейного конгруэнтного метода; б — комби-
национный генератор, заполнение исходных таблиц с помощью квантового генера-
тора случайных чисел; в — генератор «Вихрь Мерсенна»; г — случайная
последовательность слов
а
б
в
г
А.А. Лавданский, Э.В. Фауре
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 48
заполнения исходных таблиц результатом работы линейного конгруэнтного
метода, от случайной последовательности и требует дальнейшего исследования.
Рис. 4. Профиль линейной сложности: а — комбинационный генератор, заполне-
ние исходных таблиц с помощью линейного конгруэнтного метода; б — комбина-
ционный генератор, заполнение исходных таблиц с помощью квантового генерато-
ра случайных чисел; в — генератор «Вихрь Мерсенна»; г — случайная
последовательность слов
а б
Л
ин
ей
на
я
сх
од
им
ос
ть
Размер выборки Размер выборки
в г
Л
ин
ей
на
я
сх
од
им
ос
ть
Размер выборки Размер выборки
Рис. 5. Графический спектральный тест: а — комбинационный генератор, заполне-
ние исходных таблиц с помощью линейного конгруэнтного метода; б — комбина-
ционный генератор, заполнение исходных таблиц с помощью квантового генерато-
ра случайных чисел; в — генератор «Вихрь Мерсенна»; г — случайная
последовательность слов
в г
М
од
ул
ь
га
рм
он
ик
и
Номер гармоники Номер гармоники
а б
М
од
ул
ь
га
рм
он
ик
и
Номер гармоники Номер гармоники
Оценка статистических свойств последовательностей на выходе …
Системні дослідження та інформаційні технології, 2015, № 2 49
График автокорреляционной функции представлен на рис. 6. Для по-
строения графика используется битовое представление исследуемых после-
довательностей. Для тестирования взяты первые 152 бит каждой из иссле-
дуемых последовательностей.
Результаты тестирования показывают отсутствие всплесков корреля-
ции, что является успешным прохождением теста и доказывает отсутствие
внутренней корреляции для всех исследуемых последовательностей.
ВЫВОДЫ
В процессе тестирования последовательностей на выходе комбинационного
генератора получены следующие результаты: гистограмма распределения
слов последовательности подтверждает равномерное распределение слов
формируемой генератором последовательности; анализ теста распределения
на плоскости не показал каких-либо узоров на полученном изображении;
отсутствуют всплески боковых лепестков на автокорреляционной функции,
что свидетельствует об отсутствии корреляции между символами последо-
вательности; графический спектральный тест показывает отсутствие значи-
тельных всплесков гармоник; профиль линейной сложности показывает ли-
нейное увеличение сложности последовательностей по мере увеличения
размера выборки.
К
оэ
ф
ф
иц
ие
нт
ко
рр
ел
яц
ии
Величина циклического сдвигаа б
К
оэ
ф
ф
иц
ие
нт
ко
рр
ел
яц
ии
Величина циклического сдвигав г
Рис. 6. Автокорреляционная функция: а — комбинационный генератор, заполнение
исходных таблиц с помощью линейного конгруэнтного метода; б — комбинацион-
ный генератор, заполнение исходных таблиц с помощью квантового генератора
случайных чисел; в — генератор «Вихрь Мерсенна»; г — случайная последова-
тельность слов
А.А. Лавданский, Э.В. Фауре
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 50
Проведенное в работе исследование статистических свойств псевдо-
случайных последовательностей чисел показало, что последовательности,
порожденные комбинационным генератором, имеют большой период по-
вторения, успешно проходят графические тесты, являются непредсказуемы-
ми и воспроизводимыми.
ЛИТЕРАТУРА
1. Кнут Д.Э. Искусство программирования. В 4-х т. Том 2. Получисленные алго-
ритмы. — М.: Вильямс, 2007. — 832 с.
2. Митянкина Т.В., Швыдкий В.В., Фауре Э.В. Преобразование дискретных слу-
чайных процессов комбинационным автоматом // Вісник ЧДТУ. — 2004. —
№ 3. — С. 67–69.
3. Фауре Э.В. Нелинейные преобразования дискретных случайных процессов //
Радіоелектронні і комп’ютерні системи. — 2006. — № 6(18). — С. 200–205.
4. Фауре Э.В., Береза А.С., Ярославская Е.А. Оценка точности воспроизведения
закона распределения дискретной случайной величины при ее преобразова-
нии // Вiсник Хмельницького нацiонального унiверситету. — 2012. —
№ 5. — С. 176–182.
5. Elwyn R. Berlekamp. Algebraic Coding Theory. — СA: Aegean Park Press, 1984. —
474 p.
6. Massey J.L. Shift-register synthesis and BCH decoding // IEEE Trans. Information
Theory. — 1969. — IT-15. — Р. 122–127.
7. Niederreiter H. Sequences with almost perfect linear complexity profile. In D.
Chaum and W.L. Price, editors, Advances in Cryptology – EUROCRYPT ’87,
volume 304 of Lect. Notes Comput. Sci., pages 37–51, Berlin, 1987. Springer.
8. QRNG Service. — http://qrng.physik.hu-berlin.de/.
9. Береза А.С., Лавданский А.А., Швыдкий В.В., Фауре Э.В. Генерация конгруэнт-
ных последовательностей чисел с заданными свойствами // Вісник Чер-
каського державного технологічного університету. — 2012. — № 2. —
С. 3–8.
10. Matsumoto M., Nishimura T. Mersenne Twister: A 623-dimensionally equidistrib-
uted uniform pseudorandom number generator // ACM Trans. Model. Comput.
Simulat. —1998. — 8. — P. 3–30.
11. True Random Number Service.— http:// random.org/.
12. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов
псевдослучайных последовательностей. — М.: КУДИЦ-ОБРАЗ, 2003. —
240 с.
Поступила 24.06.2014
|