Помощь студентам в учебе
Исследование и реализация алгоритмов статистического моделирования
|
Введение 5
1 Алгоритмы получения псевдослучайных чисел 9
1.1 История появления первых генераторов случайных чисел и их
последовательностей 9
1.2 Устройство образования последовательностей случайных чисел ... 11
1.3 Линейный конгруэнтный метод 13
1.4 Квадратичный конгруэнтный метод 17
1.5 Линейный сдвиговый регистр с обратной связью 18
1.6 Самоуправляемый 2-линейный регистр сдвига 20
1.7 Метод серединных квадратов 22
2 Оценка качества 24
2.1 Проверка равномерности 27
2.2 Проверка стохастичности 29
2.3 Проверка независимости 30
2.4 Определение длины периода и отрезка апериодичности 31
2.5 Критерий серий 32
2.6 Критерий xi-квадрат (т2 -критерий) 33
3 Реализация и тестирование 36
3.1 Реализация мультипликативного конгруэнтного генератора 36
3.2 Реализация квадратичного конгруэнтного генератора 37
3.3 Реализация линейного сдвигового регистра с обратной связью 38
3.4 Реализация метода серединных квадратов 38
Заключение 40
Список используемой литературы 41
1 Алгоритмы получения псевдослучайных чисел 9
1.1 История появления первых генераторов случайных чисел и их
последовательностей 9
1.2 Устройство образования последовательностей случайных чисел ... 11
1.3 Линейный конгруэнтный метод 13
1.4 Квадратичный конгруэнтный метод 17
1.5 Линейный сдвиговый регистр с обратной связью 18
1.6 Самоуправляемый 2-линейный регистр сдвига 20
1.7 Метод серединных квадратов 22
2 Оценка качества 24
2.1 Проверка равномерности 27
2.2 Проверка стохастичности 29
2.3 Проверка независимости 30
2.4 Определение длины периода и отрезка апериодичности 31
2.5 Критерий серий 32
2.6 Критерий xi-квадрат (т2 -критерий) 33
3 Реализация и тестирование 36
3.1 Реализация мультипликативного конгруэнтного генератора 36
3.2 Реализация квадратичного конгруэнтного генератора 37
3.3 Реализация линейного сдвигового регистра с обратной связью 38
3.4 Реализация метода серединных квадратов 38
Заключение 40
Список используемой литературы 41
Статистическое моделирование - область математической науки, а также аналитические методология, для которой кардинальным является понятие случайной величины. Двумя наиболее важными свойствами таких величин являются случайность и непредсказуемость, о которых следовало бы рассудить по отдельности.
Первое - случайность - обретается при помощи задания некоторых статистических параметров, которые суть два критерия оценки величин в качестве случайных: однородность, то есть презумпция некоторой условно равной частоты появления каждого значения; второе - независимость - указывает на невозможность коррелирования значений последовательности между собой.
«С известной долей условности можно сказать, что не существует такого теста, что позволит нам рассудить о числах последовательности как о независимых; с другой стороны, мы имеем возможность проводить статистическое тестирование, притом формализованное в качестве некоторой стратегии, которое позволит "ухватить" взаимную зависимость.» [14]
Второе свойство — непредсказуемость. При условно "верной" трактовке случайной последовательности каждое число статистически независимо от другого. Следующий элемент последовательности, таким образом, никак не может быть предсказан исходя из значения предыдущего. Настоящая случайная последовательность — невоспроизводима. Эксперимент генерации таких последовательностей абсолютно всегда будет выдавать принципиально иной результат.
На практике, однако, источников подобных последовательностей обнаружено не очень много. Одним из наиболее "очевидных" источников могут стать, к примеру, детекторы ионизирующей радиации, на основании которых можно "ухватить" квантовое состояние частицы, чей спин и прочие параметры будут истинно случайными. Конечно, можно предположить, что каталогизация псевдослучайных величин может быть источником того же рода, однако эта интуиция порочна: мы, как операторы каталогов, можем с некоторой долей вероятности предположить последовательность каталогов.
Математический анализ при всем объеме своего инструментария не дает возможности до предела точно описать и составить последовательность "идеально" случайных чисел, поскольку значения последовательности могут быть неявным способом коррелированы. Однако подобный ригоризм не кажется необходимым: Генератор псевдослучайных чисел (последовательность которых велика до той меры, что коррелированность на сколь-нибудь исследованном участке не может быть обнаружена) достаточен для, к примеру, генерации практически непредсказуемых событий в видеоиграх.
ГПСЧ - алгоритм, работа которого возможна при наличии двух условий: семени и алгоритма. Первоначально в качестве алгоритмов ГПСЧ применялись линейные конгруэнтные генераторы. Это рекурсивные алгоритмы, которые генерируют следующую величину на основе предыдущей. Следующим логическим шагом развития линейного генератора стал так называемый "вихрь Мерсенна". Хотя псевдослучайные числа на самом деле не являются случайными, существует множество причин их использования. Во-первых, они быстры для воспроизводства. Кроме того, поскольку ГПСЧ - это просто алгоритмы, их можно проверить и всегда быть уверенным, что они работают правильно.
Эта простота - причина, по которой большинство языков использует ГПСЧ. С другой стороны, этот способ не лишён недостатков. Важнейший из них - коррелированность на предельно крупной последовательности. Эта уязвимость, к слову говоря, используется игроки, которых интересует скоростное прохождение видеоигр. Просчитав вероятность наступления конкретного события, нечестные пользователи контента могут использовать информацию для своих нужд.
Кроме того, помимо безобидных манипуляций с игровым контентом, подобные злоумышленники имеют возможность создать ключи RSA в сертификатах TLS, и в этом случае необходим более надёжный способ получения случайных чисел.
«Но бывают случаи, когда предсказание случайных чисел имеет гораздо большее значение. Например, создание ключей безопасности.
Если злоумышленник выяснит исходное значение, используемое для создания ключей RSA в сертификатах TLS, он потенциально может расшифровать сетевой трафик. Это означает, что он сможет получать пароли и другую личную информацию, передаваемую через интернет. В таких ситуациях нужен более безопасный способ получения случайных чисел. Истинно случайные числа непредсказуемы и не следуют шаблону.»[1]
«Но как компьютер может достичь этого? Как было указано ранее, компьютерам требуется внешний источник случайности. В случае ГПСЧ, это было семя. В случае ГИСЧ, это энтропия. Теория хаоса и термодинамика выходят далеко за рамки данной статьи. Достаточно сказать, что энтропия — это чистый нефильтрованный хаос. И лучший источник этого хаоса—сам компьютер. »[21]
Компьютер не может функционировать случайным образом, но составляющие его части—могут. Компьютер—это сложная система со множеством движущихся частей и изменчивостью. Тепловой шум, фотоэффект и другие квантовые явления происходят постоянно.
Но хаос был бы бесполезен, если бы его нельзя было обуздать. К счастью, инженеры-аппаратчики придумали, как это сделать. Посредством сложной схемы аппаратных микросхем и компонентов, компьютеры могут преобразовывать этот физический шум в цифровые нули и единицы.
Один из наиболее очевидных вариантов применения ГИСЧ—цифровые азартные игры. Бросание костей, перетасовка карт и вращение колеса рулетки —все это зависит от того, чтобы быть неопределимым. Хотя он часто используется при опросах общественного мнения, призыве на военную службу и отборе присяжных, а также там, где случайность используется как метод справедливости.
В действительности сферы применения ГИСЧ довольно ограничены, поскольку у них есть свой набор недостатков. Во-первых, они медлительны. Хотя это варьируется, ГИСЧ может выдавать только небольшое количество бит в секунду.
«Кроме того, ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для производства истинно случайных чисел. Но суть случайности в том, что она возникает случайным образом. Простаивающий или новый сервер не сможет генерировать числа настолько же качественно, как активный.»[18]
Первое - случайность - обретается при помощи задания некоторых статистических параметров, которые суть два критерия оценки величин в качестве случайных: однородность, то есть презумпция некоторой условно равной частоты появления каждого значения; второе - независимость - указывает на невозможность коррелирования значений последовательности между собой.
«С известной долей условности можно сказать, что не существует такого теста, что позволит нам рассудить о числах последовательности как о независимых; с другой стороны, мы имеем возможность проводить статистическое тестирование, притом формализованное в качестве некоторой стратегии, которое позволит "ухватить" взаимную зависимость.» [14]
Второе свойство — непредсказуемость. При условно "верной" трактовке случайной последовательности каждое число статистически независимо от другого. Следующий элемент последовательности, таким образом, никак не может быть предсказан исходя из значения предыдущего. Настоящая случайная последовательность — невоспроизводима. Эксперимент генерации таких последовательностей абсолютно всегда будет выдавать принципиально иной результат.
На практике, однако, источников подобных последовательностей обнаружено не очень много. Одним из наиболее "очевидных" источников могут стать, к примеру, детекторы ионизирующей радиации, на основании которых можно "ухватить" квантовое состояние частицы, чей спин и прочие параметры будут истинно случайными. Конечно, можно предположить, что каталогизация псевдослучайных величин может быть источником того же рода, однако эта интуиция порочна: мы, как операторы каталогов, можем с некоторой долей вероятности предположить последовательность каталогов.
Математический анализ при всем объеме своего инструментария не дает возможности до предела точно описать и составить последовательность "идеально" случайных чисел, поскольку значения последовательности могут быть неявным способом коррелированы. Однако подобный ригоризм не кажется необходимым: Генератор псевдослучайных чисел (последовательность которых велика до той меры, что коррелированность на сколь-нибудь исследованном участке не может быть обнаружена) достаточен для, к примеру, генерации практически непредсказуемых событий в видеоиграх.
ГПСЧ - алгоритм, работа которого возможна при наличии двух условий: семени и алгоритма. Первоначально в качестве алгоритмов ГПСЧ применялись линейные конгруэнтные генераторы. Это рекурсивные алгоритмы, которые генерируют следующую величину на основе предыдущей. Следующим логическим шагом развития линейного генератора стал так называемый "вихрь Мерсенна". Хотя псевдослучайные числа на самом деле не являются случайными, существует множество причин их использования. Во-первых, они быстры для воспроизводства. Кроме того, поскольку ГПСЧ - это просто алгоритмы, их можно проверить и всегда быть уверенным, что они работают правильно.
Эта простота - причина, по которой большинство языков использует ГПСЧ. С другой стороны, этот способ не лишён недостатков. Важнейший из них - коррелированность на предельно крупной последовательности. Эта уязвимость, к слову говоря, используется игроки, которых интересует скоростное прохождение видеоигр. Просчитав вероятность наступления конкретного события, нечестные пользователи контента могут использовать информацию для своих нужд.
Кроме того, помимо безобидных манипуляций с игровым контентом, подобные злоумышленники имеют возможность создать ключи RSA в сертификатах TLS, и в этом случае необходим более надёжный способ получения случайных чисел.
«Но бывают случаи, когда предсказание случайных чисел имеет гораздо большее значение. Например, создание ключей безопасности.
Если злоумышленник выяснит исходное значение, используемое для создания ключей RSA в сертификатах TLS, он потенциально может расшифровать сетевой трафик. Это означает, что он сможет получать пароли и другую личную информацию, передаваемую через интернет. В таких ситуациях нужен более безопасный способ получения случайных чисел. Истинно случайные числа непредсказуемы и не следуют шаблону.»[1]
«Но как компьютер может достичь этого? Как было указано ранее, компьютерам требуется внешний источник случайности. В случае ГПСЧ, это было семя. В случае ГИСЧ, это энтропия. Теория хаоса и термодинамика выходят далеко за рамки данной статьи. Достаточно сказать, что энтропия — это чистый нефильтрованный хаос. И лучший источник этого хаоса—сам компьютер. »[21]
Компьютер не может функционировать случайным образом, но составляющие его части—могут. Компьютер—это сложная система со множеством движущихся частей и изменчивостью. Тепловой шум, фотоэффект и другие квантовые явления происходят постоянно.
Но хаос был бы бесполезен, если бы его нельзя было обуздать. К счастью, инженеры-аппаратчики придумали, как это сделать. Посредством сложной схемы аппаратных микросхем и компонентов, компьютеры могут преобразовывать этот физический шум в цифровые нули и единицы.
Один из наиболее очевидных вариантов применения ГИСЧ—цифровые азартные игры. Бросание костей, перетасовка карт и вращение колеса рулетки —все это зависит от того, чтобы быть неопределимым. Хотя он часто используется при опросах общественного мнения, призыве на военную службу и отборе присяжных, а также там, где случайность используется как метод справедливости.
В действительности сферы применения ГИСЧ довольно ограничены, поскольку у них есть свой набор недостатков. Во-первых, они медлительны. Хотя это варьируется, ГИСЧ может выдавать только небольшое количество бит в секунду.
«Кроме того, ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для производства истинно случайных чисел. Но суть случайности в том, что она возникает случайным образом. Простаивающий или новый сервер не сможет генерировать числа настолько же качественно, как активный.»[18]
В нынешнее время современная информатика не может обойтись от использования псевдослучайных последовательностей. Очень важно использовать качественные генераторы для получения достойных результатов.
Взглянув на результаты можно заметить, что многие широко используемые ГСЧ имеют серьезные недостатки, в том числе генераторы по умолчанию нескольких очень популярных программных продуктов. Поэтому перед проведением важных экспериментов всегда следует проверять, какой ГСЧ используется по умолчанию, и быть готовым заменить его, если это необходимо. Перед внедрением следует убедиться, что ГСЧ имеет надежную теоретическую поддержку, что он достаточно быстр и удобен.
Среди прочего. Никакой ГСЧ не может давать гарантий от всех возможных дефектов, но следует по крайней мере, избегать тех, которые с треском проваливают простые статистические тесты, и выбирать более надежный, например, в котором после многих лет использования и тестирования не было обнаружено никаких серьезных проблем.
В работе были изучены и реализованы алгоритмы генерации псевдослучайных последовательностей. Разработан блок статистических тестов, позволяющий проверить соответствие полученной последовательности равномерному распределению, а также ее случайность и независимость. Так же была изучена и проанализирована история первых появившихся алгоритмов и генераторов, построенных на них.
Хотелось бы подчеркнуть, что данная работа актуальна для решения нестандартных задач из разных сфер деятельности. В этих сферах используются последовательности разной длинны и для разных нужд. Для этого необходимо производить эти огромные наборы чисел с разными свойствами с помощью различных генераторов.
Взглянув на результаты можно заметить, что многие широко используемые ГСЧ имеют серьезные недостатки, в том числе генераторы по умолчанию нескольких очень популярных программных продуктов. Поэтому перед проведением важных экспериментов всегда следует проверять, какой ГСЧ используется по умолчанию, и быть готовым заменить его, если это необходимо. Перед внедрением следует убедиться, что ГСЧ имеет надежную теоретическую поддержку, что он достаточно быстр и удобен.
Среди прочего. Никакой ГСЧ не может давать гарантий от всех возможных дефектов, но следует по крайней мере, избегать тех, которые с треском проваливают простые статистические тесты, и выбирать более надежный, например, в котором после многих лет использования и тестирования не было обнаружено никаких серьезных проблем.
В работе были изучены и реализованы алгоритмы генерации псевдослучайных последовательностей. Разработан блок статистических тестов, позволяющий проверить соответствие полученной последовательности равномерному распределению, а также ее случайность и независимость. Так же была изучена и проанализирована история первых появившихся алгоритмов и генераторов, построенных на них.
Хотелось бы подчеркнуть, что данная работа актуальна для решения нестандартных задач из разных сфер деятельности. В этих сферах используются последовательности разной длинны и для разных нужд. Для этого необходимо производить эти огромные наборы чисел с разными свойствами с помощью различных генераторов.