Поисковые системы
<<  Методы анализа поисковых параметров сайта Условия поиска информации, простые логические выражения  >>
Обзор алгоритмов поиска и распознавания простых чисел, информация об
Обзор алгоритмов поиска и распознавания простых чисел, информация об
Содержание
Содержание
Простое число
Простое число
Самое большое простое число
Самое большое простое число
Зачем искать простые числа
Зачем искать простые числа
Алгоритмы поиска простых чисел
Алгоритмы поиска простых чисел
Решето Эратосфена
Решето Эратосфена
Решето Эратосфена
Решето Эратосфена
Решето Сундарама
Решето Сундарама
Решето Сундарама
Решето Сундарама
Решето Аткина
Решето Аткина
Алгоритм
Алгоритм
Решето Аткина
Решето Аткина
Cравнение алгоритмов поиска простых чисел
Cравнение алгоритмов поиска простых чисел
Алгоритмы распознавания простых чисел
Алгоритмы распознавания простых чисел
Перебор делителей
Перебор делителей
Теорема Вильсона
Теорема Вильсона
Тест Ферма
Тест Ферма
Тест Пепина
Тест Пепина
Тест Миллера - Рабина
Тест Миллера - Рабина
Тест Миллера - Рабина
Тест Миллера - Рабина
Тест Миллера - Рабина
Тест Миллера - Рабина
Тест Агравала — Каяла — Саксены ( или тест AKS)
Тест Агравала — Каяла — Саксены ( или тест AKS)
Тест Агравала — Каяла — Саксены ( или тест AKS)
Тест Агравала — Каяла — Саксены ( или тест AKS)
Тест Агравала — Каяла — Саксены ( или тест AKS)
Тест Агравала — Каяла — Саксены ( или тест AKS)
Тест Агравала — Каяла — Саксены ( или тест AKS)
Тест Агравала — Каяла — Саксены ( или тест AKS)
Сравнение тестов простоты
Сравнение тестов простоты
Список литературы
Список литературы
Спасибо за внимание
Спасибо за внимание

Презентация: «Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости». Автор: Lena. Файл: «Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости.pptx». Размер zip-архива: 548 КБ.

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

содержание презентации «Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости.pptx»
СлайдТекст
1 Обзор алгоритмов поиска и распознавания простых чисел, информация об

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

их применимости.

Курицын Михаил Люлькова Елена Сизов Илья

2 Содержание

Содержание

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

2

3 Простое число

Простое число

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

3

4 Самое большое простое число

Самое большое простое число

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

4

5 Зачем искать простые числа

Зачем искать простые числа

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

5

6 Алгоритмы поиска простых чисел

Алгоритмы поиска простых чисел

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

6

7 Решето Эратосфена

Решето Эратосфена

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

Простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Алгоритм: Пусть p = 2 (первому простому числу). Считая от р, шагами по р, зачеркнуть в списке все числа от 2р до n. Найти первое не зачеркнутое число, большее чем p, и присвоить значение переменной p это число. Повторять шаги 3 и 4 до тех пор, пока p не станет больше чем n.

7

8 Решето Эратосфена

Решето Эратосфена

Сложность алгоритма:

8

9 Решето Сундарама

Решето Сундарама

1

2

3

4

5

6

7

8

9

10

i = 1, j = 1,…,6;

11

12

13

14

15

16

17

18

19

20

i = 2, j = 1,2,3;

Простые числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.

9

10 Решето Сундарама

Решето Сундарама

Обоснование

Алгоритм работает с нечётными натуральными числами большими 1, представленными в виде 2m+1, где m является натуральным числом. Если число 2m+1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть:

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

11 Решето Аткина

Решето Аткина

B основу алгоритма "решета Аткина" положены три стандартные теоремы теории элементарных чисел:

1.

2.

3.

11

12 Алгоритм

Алгоритм

Создать решето (массив соответствия простым числам для всех положительных, целых чисел начиная с 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

13 Решето Аткина

Решето Аткина

Алгоритм имеет асимптотическую сложность:

И требует следующее кол-во бит памяти:

13

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

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

14

15 Алгоритмы распознавания простых чисел

Алгоритмы распознавания простых чисел

Тесты простоты

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

15

16 Перебор делителей

Перебор делителей

Перебор делителей — алгоритм тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

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

16

17 Теорема Вильсона

Теорема Вильсона

Теорема Вильсона — теорема теории чисел, которая утверждает, что

P — простое число тогда и только тогда, когда (p ? 1)! + 1 делится на p

17

18 Тест Ферма

Тест Ферма

Основан на теореме Ферма, которая гласит:

Примечание:

Для составных p истинность равенства маловероятна.

18

19 Тест Пепина

Тест Пепина

19

20 Тест Миллера - Рабина

Тест Миллера - Рабина

Тест Миллера - Рабина - вероятностный полиномиальный тест простоты. Тест позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа.

Свидетели простоты и теорема Рабина Пусть m – нечетное число большее 1. Тогда m-1 представимо в виде:

Целое число a, 1<a<m, называется свидетелем простоты m, если выполняется одно из условий:

Или

20

21 Тест Миллера - Рабина

Тест Миллера - Рабина

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

21

22 Тест Миллера - Рабина

Тест Миллера - Рабина

Сложность алгоритма :

Однако, правильность работы алгоритма не всегда является доказанной. Вероятность, что составное число не будет выявлено за время t, обычно не превосходит

22

23 Тест Агравала — Каяла — Саксены ( или тест AKS)

Тест Агравала — Каяла — Саксены ( или тест AKS)

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

23

24 Тест Агравала — Каяла — Саксены ( или тест AKS)

Тест Агравала — Каяла — Саксены ( или тест AKS)

Основные идеи и принципы, на котором основан алгоритм AKS:

Утверждение:

24

25 Тест Агравала — Каяла — Саксены ( или тест AKS)

Тест Агравала — Каяла — Саксены ( или тест AKS)

25

26 Тест Агравала — Каяла — Саксены ( или тест AKS)

Тест Агравала — Каяла — Саксены ( или тест AKS)

Примечание:

Сложность алгоритма AKS:

26

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

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

27

28 Список литературы

Список литературы

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

28

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

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

29

«Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости»
http://900igr.net/prezentacija/informatika/obzor-algoritmov-poiska-i-raspoznavanija-prostykh-chisel-informatsija-ob-ikh-primenimosti-133966.html
cсылка на страницу

Поисковые системы

24 презентации о поисковых системах
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Поисковые системы > Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости