Отчет по лабораторной работе 1 Линейный конгруэнтный генератор. Подбор и тест параметров
 Скачать 385.76 Kb.
|
|
Министерство образования и науки Российской Федерации Санкт-Петербургский государственный политехнический университет — Институт информационных технологий и управления Кафедра «Информационная безопасность компьютерных систем» ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ № 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 |