Файл: Отчет по лабораторной работе 1 Линейный конгруэнтный генератор. Подбор и тест параметров.pdf

Министерство образования и науки Российской Федерации
Санкт-Петербургский государственный политехнический университет
—
Институт информационных технологий и управления
Кафедра «Информационная безопасность компьютерных систем»
ОТЧЕТ
ПО ЛАБОРАТОРНОЙ РАБОТЕ № 1
«Линейный конгруэнтный генератор. Подбор и тест параметров»
по дисциплине «Технологии программирования»
Выполнил студент гр.
Проверил преподаватель
Демидов Р.А.
Санкт-Петербург
2015
ФИО студента "группа"
11
1

1. ФОРМУЛИРОВКА ЗАДАНИЯ
1) Сгенерировать псевдослучайные последовательности ЛКГ. Выяснить, от чего зависит случайность последовательности. Подобрать параметры для генератора, при которых его эффективность максимальна.
2) Написать программу — генератор случайных чисел. Реализовать в ней функции rand(), srand(seed), функции для подбора подходящих параметров и тестирования произвольных, которые можно ввести с клавиатуры. Программа также должна оценивать на случайность созданную последовательность с помощью побитовых тестов, определять её максимальную мощность и период.
2. РЕЗУЛЬТАТЫ РАБОТЫ
2.1 Программа
Программа выполнена на языке программирования С. Исходный код программы представлен в приложении : Листинг 1.
Краткое описание:
функции:
1.
is_prime(x) - определяет, является ли число простым
2.
are_both_prime(a,b) — определяет, являются ли числа взаимно простыми
3.
srand(seed) — задаёт новый параметр x0 4.
get_c() - проверка, подходит ли параметр с
5.
cr_parameter() - генерация всех параметров: a,c,m.
6.
Rand() - сгенерировать случайное число
7.
period_power() - найти мощность и период у последовательности
8.
first_test() - тест на распределение битов в последовательности
9.
second_test() - частотный побитовый тест
10. third_test() - тест на одинаковые идущие подряд биты
11. demo() - вывести последовательность, протестировать её
12. enter() - ввод произвольных параметров, затем demo()
Программа начинает работу в функции main(). Создаются enum параметры для меню.
Запускается бесконечный цикл. Меню состоит из команд:
1) 0-Выход из цикла и завершение работы программы
2) 1-Сгенерировать подходящие параматры (cr_parameter())
3) 2-Тест параметров (first_test(), second_test(), third_test())
4) 3-Тест произвольных параметров (enter())
5) 4-Найти максимальную мощность и период (period_power())
6) 5-Вывести некоторое число эл-тов массива (vivod())
При нажатии опр. цифры программа выполняет поставленную задачу и возвращается к меню.
2.2 Подбор правильных параметров
Случайная последовательность генерируется по закону
,
Такая последовательность обязательно является периодической, так как число может иметь не более m различных значений, причём, длина периода не может быть больше m. Следовательно, m должен быть максимально большим.
Теорема: Максимальный период последовательности равен m, если выполняются след. условия:
1) число a-1 делится на все простые делители числа m;
2) если m делится на 4, то и a-1 делится на 4;
3) число c взаимно просто с m;
Следствие: a mod 8 = 5 ; c – нечётное, простое; m = 2^k (k=16, 32, 64).
x =( x * a + b) mod m
11
1

2.3 Тесты на случайность
Тест на идеальное распределение нулей и единиц в двоичной последовательности
Производится подсчёт единичных и нулевых битов в последовательности. В идеальной последовательности соотношение единичных и нулевых битов к общему число равно 0.5. Если отклонение от идеального распределения слишком большое (>0.1), то тест не будет пройден.
Частотный побитовый тест
Вероятность ошибки первого рода называют уровнем статистической значимости и обозначают как α. Т.е. α — это вероятность отбраковать «хорошую» случайную последовательность.
Это значение определяется областью применения. В криптографии принято α брать от 0.001 до 0.01.
В каждом тесте вычисляется P-значение: это вероятность того, что подопытный генератор произведет последовательность не хуже, чем гипотетический истинный. Если P - значение = 1, то наша последовательность идеально случайна, а если оно = 0, то последовательность полностью предсказуема.
В дальнейшем P-значение сравнивается с α, и если она больше α, то нулевая гипотеза принимается и последовательность признается случайной. В противном случае — отбраковывается.
В тестах берется α = 0.01. Из этого следует, что: Если P-значение ≥ 0.01, то последовательность признается случайной с уровнем доверия 99%. Если P-значение < 0.01, то последовательность отбраковывается с уровнем доверия 99%. Очевидно, что чем более случайна последовательность, тем ближе это соотношение к 1. Данный тест оценивает, насколько P близко к 1.
Тест на одинаковые идущие подряд биты
В тесте ищутся все последовательности одинаковых битов, а затем анализируется, насколько количество и размеры этих последовательностей соответствуют количеству и размерам истинно случайной последовательности. Смысл в том, что если смена 0 на 1 (и обратно) происходит слишом редко, то такая последовательность «не тянет» на случайную.
2.4 Виды параметров
Подбираемые параметры можно разделить на 3 типа: Отличные, хорошие, плохие.
Рассмотрим каждый тип:
•
Отличные
Это параметры, полностью удовлетворяющие условиям теоремы. Все битовые тесты проходят успешно, суммарное распределение битов близко к 0.5 в каждом из двоичных разрядов.
Достигается максимальный период, мощность >=5. Все различные числа в последовательности встречаются ровно по одному разу.Всё вышеперечисленное свидетельствует о хорошем генераторе. Пример — a = 6645; c = 2543; m = 65536
•
Хорошие
Это параметры, частично удовлетворяющие условиям теоремы.
Все битовые тесты проходят успешно, суммарное распределение битов близко к 0.4 на 0.6 или
0.5 в большинстве или каждом из двоичных разрядов.
Некоторые из таких параметров можно было бы определить, как отличные, но их отличие — невозможность существования максимального периода и частота встречаемости (число может встретиться более 1 раза, а может и вообще не встретиться).
Пример — a = 91; c = 91; m = 65536 (настоящий период равен 32768)
•
Плохие
Данный тип параметров не удовлетворяет условиям теоремы, проваливает тесты. Имеет маленький период. Суммарное количество нулей и единиц в старших двоичных разрядах сильно отличается. Последовательность визуально не выглядит случайной или вообще вырождается.
Пример — a = 28; c = 2; m = 45.
11
1

3. ВЫВОДЫ
Линейный конгруэнтный метод довольно продуктивен и используется во многих компиляторах.
Он порождает статистически хорошую псевдослучайную последовательность чисел, если правильно выбрать параметры для генератора. Опыты показывают, что максимальную эффективность он показывает при параметрах, удовлетворяющих условиям теоремы о макс. периоде. Если же некоторые параметры не будут удовлетворять условиям, то оценка случайности генератора останется хорошей,
однако макс. период в этом случае будет меньше ожидаемого. При плохих параметрах ясно видна периодичная зависимость между элементами последовательности.
Приложение
Листинг 1:
#include
#include
#include
#include
#define RAND_MAX 65536
// простое ли int is_prime(int x)
{
if (x != 0)
{
for (int i = 2; i <= x / 2; i++)
if (x % i == 0)
return 0;
}
return 1;
}
//взаимно простые int are_both_prime(int a, int b)
{
while (a && b)
{
if (a >= b)
a %= b;
else b %= a;
}
return (a | b) == 1 ? 1 : 0;
}
int m = RAND_MAX, a = 1537, c = 0, x = 5289, x0;
int ar[RAND_MAX] = { 0 };
int b[RAND_MAX] = { 0 };
void srand(int seed)
{
x = seed;
}
// проверка условий с int get_c()
{
if (c % 2 == 0 || !are_both_prime(m, c))
return 0;
return 1;
}//подобрать с
// создать параметры void cr_parameter()
{
m = RAND_MAX;
a = 1 + clock() % 32767;
c = 1 + clock() % 4096;
printf("Теорема о макс. периоде:\n");
printf("По усл. теоремы параметры c,m должны быть взаимно простыми\n");
printf("По усл. теоремы а-1 должен делиться нацело на любое простое р, на которое нацело делится m\n");
printf("По усл. теоремы а-1 должен нацело делиться на 4, если m делится нацело на 4\n");
printf("Следствие из теоремы: a mod 8 = 5\n");
int good_parameter = 0;
while (!good_parameter)
{
c++;
good_parameter = get_c();
}
11
1

// c podobran good_parameter = 0;
while (good_parameter!=1)
{
a++;
if (a % 8 == 5)
good_parameter = 1;
}
// a podobran printf("\nа = %d, m = %d, c = %d. Эти параметры удовлетворяют условиям теоремы\n", a, m, c);
}// сгенерировать подходящие параметры
//true int Rand()
{
x = (a*x + c) % m;
return x;
}
// мощность и период void period_power()
{
x = x0;
int i = 1;
printf("Последовательность с параметрами а = %d, с = %d, m = %d\n", a, c, m);
for (i = 0; i < RAND_MAX; i++)
{
if (i < 100)
printf("%d ", ar[i] = Rand());
else ar[i] = Rand();
}
printf("... и ещё 65435 эл-тов");
int freq[RAND_MAX] = { 0 };
int period_val = RAND_MAX;
short found = 0;
for (i = 0; i < RAND_MAX; i++)
{
freq[ar[i]]++;
if (freq[ar[i]] > 1)
{
period_val = i;
for (i = 0; i < period_val; i++)
if (ar[period_val] == ar[i])
{
if (ar[i] == ar[i + 1] && ar[i] == ar[i + 2])
{
period_val = i;
printf("\n\nПоследовательность вырождается. %d эл. до вырождения\n", period_val);
found = 1; break;
}
else if (ar[period_val + 1] == ar[i + 1] && ar[period_val +
2] == ar[i + 2])
{
period_val -= i;
printf("\n\nМаксимальный период последовательности равен %d\n", period_val);
found = 1; break;
}
else
{
period_val = RAND_MAX;
i = period_val + 1;
}
}
}
if (found)
break;
}
double got = 0;
double power = 0;
while (modf(pow(a - 1, power) / m, &got) && power < 30)
power++;
if (!found)
printf("\n\nМаксимальный период последовательности равен %d\n", period_val);
11
1

printf( (power>=29) ? "\nМаксимальная мощность последовательности не может быть точно вычислена \n" :
"\nМаксимальная мощность последовательности = %d", (int)power);
printf("\nБольшая мощность не гарантирует хорошей последовательности \n");
}
//тесты int first_test()
{
float n0 = 0, n1 = 0;
int one[15] = { 0 }; // razryadi int null[15] = { 0 };
for (int i = 0; i < m; i++)
{
for (int j = 0; j < 15; j++)
{
if (((1 << j) & ar[i]) == 0)
{
n0++;
null[j]++;
}
else
{
n1++;
one[j]++;
}
}
}
printf("\nСуммарное кол-во 0 и 1 в двоичных разрядах по %d числам:\n", m);
for (int i = 0; i < 15; i++)
printf("В разряде %d число единиц равно %d, число нулей равно %d\n", i, one[i], null[i]);
printf("\n");
printf("В последовательности распределение единичных битов равно %lf\n", n1/(n1+n0));
printf("В последовательности распределение нулевых битов равно %lf\n", n0/(n1+n0));
printf("Идеальное распределение должно содержать 0.5 бит каждого вида\n");
if (fabs(n1 / (n1 + n0) - n0/(n1+n0)) < 0.1)
{
printf("\nТест 1 о допустимом распределении битов в последовательности пройден\n");
return 1;
}
else
{
printf("\nТест 1 о допустимом распределении битов в последовательности провален\n");
return 0;
}
}
int second_test()
{
double s = 0;
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 15; j++)
{
if (((1 << j) & ar[i]) == 0)
s -= 1;
else s += 1;
}
}
s = fabs(s) / sqrt(100 * 15);
if (erfc(s / sqrt(2)) > 0.01)
{
printf("\nЧастотный побитовый тест 2 пройден\n");
return 1;
}
else
{
printf("\nЧастотный побитовый тест 2 провален\n");
return 0;
}
}
int third_test()
{
double p = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < 15; j++)
{
11
1

if (((1 << j) & ar[i]) != 0)
p += 1;
}
}
p /= m * 16;
if (fabs(p - 0.5) > 2 / sqrt(p))
{
printf("\nТест 3 на одинаковые идущие подряд биты провален\n");
return 0;
}
else
{
int rk;
int Vn = 0;
for (int i = 0; i <50; i++)
{
for (int j = 1; j < 16; j++)
{
if (((1 << j - 1) & ar[i]) != 0 && ((1 << j) & ar[i]) != 0)
rk = 0;
else if (((1 << j) & ar[i]) == 0 && ((1 << j - 1) & ar[i]) == 0)
rk = 0;
else rk = 1;
Vn += rk;
}
Vn++;
if (erfc(fabs((Vn - (2 * p*(1 - p)*m)) / (2 * p*(1 - p)*sqrt(2 * m * 16))) / 100) <
0.01)
{
printf("\nТест 3 на одинаковые идущие подряд биты провален\n");
return 0;
}
Vn = 0;
}
printf("\nТест 3 на одинаковые идущие подряд биты пройден\n");
return 1;
}
}
// запустить тест последовательности void demo()
{
int freq[RAND_MAX] = { 0 };
printf("Последовательность с параметрами а = %d, с = %d, m = %d\n", a, c, m);
for (int i = 0; i < RAND_MAX; i++)
{
if (i < 100)
printf("%d ", ar[i] = Rand());
else ar[i] = Rand();
freq[ar[i]]++;
}
printf("... и ещё 65435 эл-тов");
printf("\nПохожа ли она на случайную?\n");
//
int min = ar[0], max = ar[0], freq_min=-1, freq_max=-1;
for (int i = 0; i < RAND_MAX; i++)
if (freq[ar[i]] > freq_max )
{
max = ar[i];
freq_max = freq[ar[i]];
}
freq_min = freq_max;
for (int i = 0; i < RAND_MAX; i++)
if (freq[i] < freq_min)
{
min = i;
freq_min = freq[i];
}
printf("\nМаксимум: число %d встречается %d раз\nМинимум: число %d встречается %d раз\n", max,
freq_max, min, freq_min);
//printf("\n %d %d \n", max, freq_max, min, freq_min);
//
if (first_test(ar) && second_test(ar) && third_test(ar))
printf("\nХороший генератор\n");
11
1

else printf("\nПлохой генератор\n");
}//проверка с тестами
// ввести свои параметры void enter()
{
do printf((printf("Параметр a= "), scanf("%d", &a), a < 0 || a>RAND_MAX) ? "Недопустимое число\n" : "");
while (a < 0 || a>RAND_MAX);
do printf((printf("Параметр c= "), scanf("%d", &c), c < 0 || c>RAND_MAX) ? "Недопустимое число\n" : "");
while (c < 0 || c>RAND_MAX);
do printf((printf("Параметр m= "), scanf("%d", &m), m <= 0 || m>RAND_MAX) ? "Недопустимое число\n" :
"");
while (m <= 0 || m>RAND_MAX);
do printf((printf("Параметр x0= "), scanf("%d", &x), x < 0 || x>RAND_MAX) ? "Недопустимое число\n" :
"");
while (x < 0 || x>RAND_MAX);
x0 = x;
demo();
}//свой ввод параметров
//
void vivod1()
{
int k=0;
do
{
printf("Вывести элементов: ");
scanf("%d", &k);
} while (k < 0 || k>RAND_MAX);
for (int i = 0; i < k; i++)
printf("%d\t",ar[i]);
printf("\n");
}
int main()
{
setlocale(LC_ALL, "rus");
enum menu { out, create, test, vvod, pp , vivod };
//printf("%d %d\n", out, vvod);
printf("Вас приветствует программа - генератор случайных чисел\n");
int err = 1;
while (1)
{
printf("\n\n0-Выход\n1-Сгенерировать подходящие параматры\n2-Тест параметров\n3-Тест произвольных параметров\n4-Найти макс. мощность и период\n5-Вывести эл-ты массива\n\n");
int choose;
scanf("%d", &choose);
switch (choose)
{
case out: { return 0; }
case create: { cr_parameter(); err = 0; break; }
case test: { (err == 0) ? demo() : printf("Сначала нужно создать параметры генератора или ввести их вручную\n"); break; }
case vvod: { enter(); err = 0; break; }
case pp: { (err == 0) ? period_power() : printf("Сначала нужно создать параметры генератора или ввести их вручную\n"); break; }
case vivod: {vivod1(); break; }
default: { printf("Такой команды не существует\n"); break; }
}
}
getchar();
return 0;
}
11
1

11
1