О БЗОР АЛГОРИТМОВ ПОИСКА И РАСПОЗНАВАНИЯ ПРОСТЫХ ЧИСЕЛ, ИНФОРМАЦИЯ ОБ ИХ ПРИМЕНИМОСТИ. Курицын Михаил Люлькова Елена Сизов Илья

С ОДЕРЖАНИЕ Простое число Зачем искать простые числа? Алгоритмы поиска простых чисел Сравнение алгоритмов поиска простых чисел Алгоритмы распознавания простых чисел. Тесты простоты. Алгоритмы распознавания простых чисел. Тесты простоты. Сравнение тестов простоты Список литературы 2

П РОСТОЕ ЧИСЛО Простое число – это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Остальные числа, кроме единицы, называются составными. Последовательность простых чисел начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … 3

С АМОЕ БОЛЬШОЕ ПРОСТОЕ ЧИСЛО Один из рекордов поставил в своё время Эйлер, найдя простое число = Наибольшим известным простым числом по состоянию на февраль 2011 года является За нахождение простых чисел из более чем и десятичных цифр EFF назначила денежные призы соответственно в и долларов. 4

З АЧЕМ ИСКАТЬ ПРОСТЫЕ ЧИСЛА ? Криптография – наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства) информации. Криптография изучает методы шифрования информации – преобразования открытого текста на основе секретного алгоритма и/или ключа в шифрованный текст. В криптографических алгоритмах одной из важных задач является проверка на простоту, т.е. умение быстро отличить просто число от составного. 5

А ЛГОРИТМЫ ПОИСКА ПРОСТЫХ ЧИСЕЛ Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают : Решето Эратосфена Решето Сундарама Решето Аткина 6

7 Р ЕШЕТО Э РАТОСФЕНА Алгоритм: 1.Пусть p = 2 (первому простому числу). 2.Считая от р, шагами по р, зачеркнуть в списке все числа от 2р до n. 3.Найти первое не зачеркнутое число, большее чем p, и присвоить значение переменной p это число. 4.Повторять шаги 3 и 4 до тех пор, пока p не станет больше чем n. Простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Р ЕШЕТО Э РАТОСФЕНА Сложность алгоритма: 8

Р ЕШЕТО С УНДАРАМА i = 1, j = 1,…,6; i = 2, j = 1,2,3; Простые числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.

Р ЕШЕТО С УНДАРАМА. О БОСНОВАНИЕ Алгоритм работает с нечётными натуральными числами большими 1, представленными в виде 2 m +1, где m является натуральным числом. Если число 2 m +1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть: 10 2 m +1 = (2 i +1)(2 j +1), где i, j – натуральные числа m = 2 ij + i + j Что эквивалентно: Если из ряда натуральных чисел исключить все числа вида 2ij + i + j,, то для каждого из оставшихся чисел m число 2 m +1 обязано быть простым. Если число 2 m +1 является простым, то число m невозможно представить в виде 2 ij + i + j и, таким образом, m не будет исключено в процессе работы алгоритма.

Р ЕШЕТО А ТКИНА B основу алгоритма "решета Аткина" положены три стандартные теоремы теории элементарных чисел:

А ЛГОРИТМ Создать решето (массив соответствия простым числам для всех положительных, целых чисел начиная с 2). Изначально все элементы решета помечаются как составные. Для каждого числа n в решете, если остаток от деления по модулю 60: Равен 1, 13, 17, 29, 37, 41, 49, или 53, и n = 4 * x 2 + y 2 поменять значение в решете на противоположное. Равен 7, 19, 31, или 43, и n = 3 * x 2 + y 2 ; поменять значение решете на противоположное. Равен 11, 23, 47, или 59, и n = 3 * x 2 - y 2 при(x > y); поменять значение в решете на противоположное. (х и у целые, положительные числа) Взять наименьшее число из решета, помеченное как простое, и пометить все элементы решета, кратные квадрату этого простого числа как составные. Повторить шаг 3 12

Р ЕШЕТО А ТКИНА Алгоритм имеет асимптотическую сложность: 13 и требует следующее кол-во бит памяти:

C РАВНЕНИЕ АЛГОРИТМОВ ПОИСКА ПРОСТЫХ ЧИСЕЛ 14

А ЛГОРИТМЫ РАСПОЗНАВАНИЯ ПРОСТЫХ ЧИСЕЛ. Т ЕСТЫ ПРОСТОТЫ Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Перебор делителей Теорема Вильсона Тест Ферма Тест Пепина Тест Миллера – Рабина Тест Агравала – Каяла – Саксены 15

П ЕРЕБОР ДЕЛИТЕЛЕЙ Перебор делителей алгоритм тестирования простоты числа путем полного перебора всех возможных потенциальных делителей. 16 Алгоритм: 1.Перебор всех целых чисел от 2 до квадратного корня из числа n и вычисление остатка от деления n на каждое из этих чисел. 2.Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу. 3.По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.

Т ЕОРЕМА В ИЛЬСОНА Теорема Вильсона теорема теории чисел, которая утверждает, что 17 p простое число тогда и только тогда, когда ( p 1)! + 1 делится на p

Т ЕСТ Ф ЕРМА Основан на теореме Ферма, которая гласит: 18 Для составных p истинность равенства маловероятна. Примечание:

Т ЕСТ П ЕПИНА 19

Т ЕСТ М ИЛЛЕРА - Р АБИНА Тест Миллера - Рабина - вероятностный полиномиальный тест простоты. Тест позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. 20 Свидетели простоты и теорема Рабина Пусть m – нечетное число большее 1. Тогда m-1 представимо в виде: Целое число a, 1

Т ЕСТ М ИЛЛЕРА - Р АБИНА 21 Алгоритм: Параметром алгоритма Миллера – Рабина является количество раундов r. В каждом раунде выполняются следующие действия: 1.Выбирается случайное число a, 2 < a < m-1. 2.Если a не является свидетелем простоты числа m, то выдается ответ «m составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. 3.После нахождения r свидетелей простоты, выдается ответ «m, вероятно, простое», и алгоритм завершается.

Т ЕСТ М ИЛЛЕРА - Р АБИНА Сложность алгоритма : 22 Однако, правильность работы алгоритма не всегда является доказанной. Вероятность, что составное число не будет выявлено за время t, обычно не превосходит

Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) Универсальность : Тест AKS может использоваться для проверки простоты любых чисел. Полиномиальность : Наибольшее время работы алгоритма ограничено полиномом от количества цифр в проверяемом числе. Детерминизм : Алгоритм гарантирует получение ответа. Безусловность : Корректность теста AKS не зависит от каких-либо недоказанных гипотез. 23

Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) Основные идеи и принципы, на котором основан алгоритм AKS: 24 Утверждение:

Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) 25

Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) Сложность алгоритма AKS: 26 Примечание:

С РАВНЕНИЕ ТЕСТОВ ПРОСТОТЫ 27

С ПИСОК ЛИТЕРАТУРЫ Википедия Л. Бараш, Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел. С.В. Сизый, Лекции по теории чисел. С. Г. Гиндикин, Малая теорема Ферма / Квант A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms. – И.В.Агафонова, Проверка чисел на простоту: полиномиальный алгоритм. Б.А. Фороузан, Математика криптографии и теория шифрования. 28

С ПАСИБО ЗА ВНИМАНИЕ ! 29