Тестирование псевдослучайных последовательностей (ПСП) - совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т.п.
Существует несколько методов тестирования ПСП:
. Графический тест.
К этой категории относятся тесты, результаты которых отображаются в виде графиков, характеризующих свойства исследуемой последовательности. Среди них:
а) гистограмма распределения элементов последовательности (позволяет оценить равномерность распределения символов в последовательности и определить частоту повторения каждого символа);
б) распределение на плоскости (предназначено для определения зависимости между элементами последовательности);
в) проверка серий (позволяет определить равномерность отдельных символов в последовательности, а так же равномерность распределения серий из k бит);
г) проверка на монотонность.
. Статистический тест.
В отличие от графических тестов, статистические тесты выдают численную характеристику последовательности и позволяют однозначно сказать, пройден ли тест.
4. Генератор случайных чисел в Borland C++
В языках программирования обычно предусмотрены функции, позволяющие генерировать случайные числа в определенном по умолчанию диапазоне. На самом деле генерируются не случайные, а так называемые псевдослучайные числа; они выглядят случайно, но вычисляются по вполне конкретной формуле. Но для простоты далее мы все равно будем называть их случайными.
В Borland C++ (как и во многих других реализациях C/C++) используется линейный конгруэнтный ГСЧ. Длина периода этого ГСЧ составляет 232 числа.
В языке программирования C получить случайное число можно с помощью функции rand (), которая входит в стандартную библиотеку языка. Эта функция не принимает никакие параметры. Функция rand () возвращает целое число от 0 до значения присвоенного константе RAND_MAX. Значение RAND_MAX зависит от системы и определено в заголовочном файле stdlib. h. Так, например, оно может быть равно 32767 (двухбайтовое целое) или 2147483647 (четырехбайтовое целое).
Код ниже выводит на экран 50 случайных чисел:
#include <stdio. h>
#include <stdlib. h>() {i;(i = 1; i <= 50; i++) {("%15d", rand ());(i % 5 == 0) printf ("\n");
}
}
В теле цикла осуществляется переход на новую строку после каждых выведенных на экран пяти чисел. Для этого используется выражение, в котором находится остаток от деления i на 5, результат сравнивается с 0. Чтобы после первого числа не происходил переход на новую строку, i сначала присваивается единица, а не ноль (т.к.0 делится на 5 без остатка).
При каждом запуске программы числа остаются одинаковыми. Даже если вы перекомпилируете программу, результат не изменится. Данный эффект связан с тем, что начальное (инициализирующее) число, которое подставляется в формулу вычисления первого и последующих псевдослучайных чисел, для каждой системы всегда одно и то же.
Однако это начальное число можно изменить с помощью функции srand (), которой в качестве параметра передается любое целое число. Инициализирующее значение привязывают к какому-либо процессу, протекающему в операционной системе, например, к часам. Время (учитывая не только время суток, но и дату) никогда не бывает одинаковым. Значит значение для srand (), преобразованное в целое из системного времени, будет различным.
Текущее время можно узнать с помощью функции time (), прототип которой описан в файле time. h. Передав time () в качестве параметра NULL, мы получим целое число, которое можно передать в srand ():(time (NULL));
Ситуация с вещественными числами выглядит несколько по-иному. Во-первых, мы не можем получить остаток от деления, если делимое или делитель дробное число. Во вторых при вычислении длины диапазона нельзя прибавлять единицу. Таким образом формула для получения случайного вещественного числа выглядит так:
(float) rand () / RAND_MAX * (max - min) + min
Функция rand () генерирует любое случайное число от 0 до RAND_MAX с равной долей вероятности. Другими словами, у числа 100 есть такой же шанс выпасть, как и у числа 25876.
Чтобы доказать это, достаточно написать программу, подсчитывающую количество выпадений каждого из значений. Если выборка (количество "испытуемых") будет достаточно большой, а диапазон (разброс значений) маленьким, то мы должны увидеть, что процент выпадений того или иного значения приблизительно такой же как у других.
#include <stdio. h>
#include <time. h>
#define N 500() {i;arr [5] = {0};(time (NULL));(i=0; i < N; i++)(rand () % 5) {0: arr [0] ++; break;1: arr [1] ++; break;2: arr [2] ++; break;3: arr [3] ++; break;4: arr [4] ++; break;
}(i=0; i < 5; i++)("%d - %.2f%%\n", i, ((float) arr [i] / N) * 100);
}
В приведенной программе массив из пяти элементов сначала заполняется нулями. Случайные числа генерируются от 0 до 4 включительно. Если выпадает число 0, то увеличивается значение первого элемента массива, если число 1, то второго, и т.д. В конце на экран выводится процент выпадения каждого из чисел.
Заключение
Современная информатика широко использует псевдослучайные числа в самых различных приложениях. При этом от качества используемых генераторов псевдослучайных чисел зависит качество получаемых результатов.
Одной из важнейших задач математической статистики является установление теоретического закона распределения случайной величины, характеризующей изучаемый признак по опытному (эмпирическому) распределению, представляющему вариационный ряд.
Генерирование случайных последовательностей с заданным вероятностным законом и проверка их адекватности - одни из важнейших проблем современной криптологии. Генераторы случайных последовательностей используются в существующих криптосистемах для генерации ключевой информации и задания ряда параметров криптосистем.
В начале XX века случайные последовательности имитировались с помощью простейших случайных экспериментов: бросание монеты или игральной кости, извлечение шаров из урны, раскладывание карт, рулетка и т.д. В 1927 г.Л. Типпетом впервые были опубликованы таблицы, содержащие свыше 40000 случайных цифр, "произвольно извлечённых из отчётов о переписи населения". В 1939 г. с помощью специально сконструированного механического устройства - генератора случайных чисел, М. Дж. Кендалл и Б. Бэбингтон-Смит создали таблицу, включающую 105 случайных цифр. В 1946 г. американский математик Джон фон Нейман впервые предложил компьютерный алгоритм генерации случайных чисел. В 1955 г. компания RAND Corporation опубликовала получившие широкую популярность таблицы, содержащие 106 случайных цифр, сгенерированных на ЭВМ.