'

Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости.

Понравилась презентация – покажи это...





Слайд 0

Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости. Курицын Михаил Люлькова Елена Сизов Илья


Слайд 1

Содержание Простое число Зачем искать простые числа? Алгоритмы поиска простых чисел Сравнение алгоритмов поиска простых чисел Алгоритмы распознавания простых чисел. Тесты простоты. Сравнение тестов простоты Список литературы 2


Слайд 2

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


Слайд 3

Самое большое простое число Один из рекордов поставил в своё время Эйлер, найдя простое число 231 ? 1 = 2147483647. Наибольшим известным простым числом по состоянию на февраль 2011 года является 243112609 ? 1 За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 долларов. 4


Слайд 4

Зачем искать простые числа? Криптография – наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства) информации. Криптография изучает методы шифрования информации  – преобразования открытого текста на основе секретного алгоритма и/или ключа в шифрованный текст. В криптографических алгоритмах одной из важных задач является проверка на простоту, т.е. умение быстро отличить просто число от составного. 5


Слайд 5

Алгоритмы поиска простых чисел Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают : Решето Эратосфена Решето Сундарама Решето Аткина 6


Слайд 6

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


Слайд 7

Решето Эратосфена Сложность алгоритма: 8 O( n? ?????? 2 ?????? 2 (??))


Слайд 8

Решето Сундарама 9 Алгоритм: Из ряда натуральных чисел от 1 до N исключаются все числа вида i + j + 2ij ( i = 1,2, ,…, 2??+1 ?1 2 ; j = i,i+1,…, ????? 2??+1 ). Каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все нечётные простые числа в отрезке [1,2N+1]. i = 1, j = 1,…,6; i = 2, j = 1,2,3; Простые числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.


Слайд 9

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


Слайд 10

Решето Аткина B основу алгоритма "решета Аткина" положены три стандартные теоремы теории элементарных чисел: 11 n – простое, если: 4? ?? 2 + ?? 2 =?? (??>0, ??>0) n mod 4 = 1 n – нечетное число n – простое, если: 3? ?? 2 + ?? 2 =?? (??>0, ??>0) n mod 6 = 1 n – нечетное число n – простое, если: 3? ?? 2 ? ?? 2 =?? (??>0, ??>0) n mod 12 = 11 n – нечетное число 1. 2. 3.


Слайд 11

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


Слайд 12

Решето Аткина Алгоритм имеет асимптотическую сложность: 13 ??( ?? log log ?? ) и требует следующее кол-во бит памяти: O ( ?? 1 2 +??(1) )


Слайд 13

Cравнение алгоритмов поиска простых чисел 14


Слайд 14

Алгоритмы распознавания простых чисел. Тесты простоты Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Перебор делителей Теорема Вильсона Тест Ферма Тест Пепина Тест Миллера – Рабина Тест Агравала – Каяла – Саксены 15


Слайд 15

Перебор делителей Перебор делителей — алгоритм тестирования простоты числа путем полного перебора всех возможных потенциальных делителей. 16 Алгоритм: Перебор всех целых чисел от 2 до квадратного корня из числа n и вычисление остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу. По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.


Слайд 16

Теорема Вильсона Теорема Вильсона — теорема теории чисел, которая утверждает, что 17 p — простое число тогда и только тогда, когда (p ? 1)! + 1 делится на p


Слайд 17

Тест Ферма Основан на теореме Ферма, которая гласит: 18 Если p – простое число, то для любого целого a выполняется равенство ?? ???1 ?1(?????? ??) или ( ?? ???1 ?1) делится на ?? нацело. Для составных p истинность равенства маловероятна. Примечание:


Слайд 18

Тест Пепина Тест пепина является тестом простоты для чисел Ферма. Число ферма – это число вида: ?? ?? = 2 2 ?? +1, ?? – целое, неотрицательное. Число Ферма является простым тогда и только тогда, когда ?? ( ?? ?? ???)/?? ???? (?????? ?? ?? ). На сегодняшний день известно только 5 простых чисел Ферма: 3, 5, 17, 257 и 65537. 19


Слайд 19

Тест Миллера - Рабина Тест Миллера - Рабина - вероятностный полиномиальный тест простоты. Тест позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. 20 Свидетели простоты и теорема Рабина Пусть m – нечетное число большее 1. Тогда m-1 представимо в виде: m-1 = 2 ?? *t , где t – нечетно Целое число a, 1<a<m, называется свидетелем простоты m, если выполняется одно из условий: ?? ?? mod m = 1 существует такое r, (?? ?? ) 2 ?? mod m=?1 или


Слайд 20

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


Слайд 21

Тест Миллера - Рабина Сложность алгоритма : 22 O (?????? 3 ??) Однако, правильность работы алгоритма не всегда является доказанной. Вероятность, что составное число не будет выявлено за время t, обычно не превосходит ?? ?????


Слайд 22

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


Слайд 23

Тест Агравала — Каяла — Саксены ( или тест AKS) Основные идеи и принципы, на котором основан алгоритм AKS: 24 n – простое тогда и только тогда, когда: НОД (a, n) = 1 (?????) ?? ?( ?? ?? ???)(?????? ??) Теорема AKS Пусть ???2;???целое; ??,?? ?простые числа , причем ???? 1,2,..,?? :НОД ??,?? =1 q – наибольший простой делитель (r-1) ???4? ?? ?????? 2 ?? ?? (???1)/?? !?1 ?????? ?? ??? 1,2,…,2? ?? ?????? 2 ?? +1 : ????? ?? ? ?? ?? ??? ?????? ??, ?? ?? ?1 Тогда n – степень простого числа. Утверждение:


Слайд 24

Тест Агравала — Каяла — Саксены ( или тест AKS) Алгоритм: ?? = 2 ?????????(??<??){ ????(НОД(?? , ??)?1) вернуть составное; ???? ??? простое , ?? >2 { ?? – наибольший простой делитель у (???1); ???? ?? ?4 ?? ?????? 2 ?? ?????? ( ?? ???1 ?? ?1(?????? ??))) ??????????; } ?? = ??+1; } ?????? ?? = 1 ???? ( 2 ?? ?????? 2 ?? +1) ???? ????? ?? ? ?? ?? ??? ?????? ?? ?? ?1,?? вернуть составное; ???? ?? = ?? ?? ;??,?? ?целые;??,???2 вернуть составное; вернуть простое; 25


Слайд 25

Тест Агравала — Каяла — Саксены ( или тест AKS) Сложность алгоритма AKS: 26 O ( ?????? 19 ??) Примечание: Выражение: ????? ?? ? ?? ?? ??? ?????? ?? ?? ?1,?? означает следующее: для многочленов (?????) ?? и ?? ?? ??? найдется многочлен ?? ?? ???? ?? (кольцо многочленов от x с целыми коэффициентами) такой, что все коэффициенты многочлена (?????) ?? ? ?? ?? ??? ? ?? ?? ?1 ??? ?? кратны ??.


Слайд 26

Сравнение тестов простоты 27


Слайд 27

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


Слайд 28

Спасибо за внимание! 29


×

HTML:





Ссылка: