Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Презентации / Презентация на тему "Простые числа в криптографии. Волшебное решето Эратосфена"

Презентация на тему "Простые числа в криптографии. Волшебное решето Эратосфена"

  • Информатика
Автор проекта: учитель информатики и ИКТ МБОУ «Школа №58» г. Нижнего Новгород...
1 2 3 9 4 5 6 7 8 10
Справка о предмете исследования Просто́е число́ — это натуральное число, кото...
Более двух тысяч лет назад великий древнегреческий математик Евклид доказал,...
Для людей поиск простых чисел превратился в целенаправленный отбор отдельных...
За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичн...
Криптография - наука о способах преобразования (шифрования) информации с цель...
Шифрование, защита информации актуальны в политике, экономике, бизнесе и про...
Напомню, что математикам до сих пор не удавалось обнаружить какой-либо систем...
Если такие «кластеры» будут найдены, стойкость криптографических ключей, исп...
В поиске простых чисел весьма полезным оказался метод, восходящий еще к древн...
Эратосфен придумал для поиска простых чисел следующий способ: Сначала вычерки...
В математике Эратосфена интересовал вопрос о том, как найти все простые числ...
В поисках истины Первый алгоритм поиска простых чисел, приходящий в голову, п...
Рассмотрим недостатки данного алгоритма: В Паскале по некоторым причинам резу...
Суть дальнейшего и главного улучшения алгоритма вычисления множества простых...
Варианты реализации алгоритма поиска простых чисел «Решето Эратосфена» В Паск...
C помощью множества Множество целых чисел не превышает значения 255. Если чис...
C помощью массива Лучше использовать массив с элементами логического типа. Бу...
C помощью строк Будем считать, что на i-ом месте строки S стоит '*' если числ...
На этих примерах видно, какие есть возможности у Паскаля для реализации алгор...
http://ru.wikipedia.org/wiki/Простое_число http://ru.wikipedia.org/wiki/Решет...
1 из 23

Описание презентации по отдельным слайдам:

№ слайда 1 Автор проекта: учитель информатики и ИКТ МБОУ «Школа №58» г. Нижнего Новгород
Описание слайда:

Автор проекта: учитель информатики и ИКТ МБОУ «Школа №58» г. Нижнего Новгорода Иванцова Светлана Анатольевна 2016 г. Простые числа в криптографии. Волшебное решето Эратосфена.

№ слайда 2 1 2 3 9 4 5 6 7 8 10
Описание слайда:

1 2 3 9 4 5 6 7 8 10

№ слайда 3 Справка о предмете исследования Просто́е число́ — это натуральное число, кото
Описание слайда:

Справка о предмете исследования Просто́е число́ — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Число 1 не относится ни к простым, ни к составным числам. Последовательность простых чисел начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, …

№ слайда 4 Более двух тысяч лет назад великий древнегреческий математик Евклид доказал,
Описание слайда:

Более двух тысяч лет назад великий древнегреческий математик Евклид доказал, что ряд простых чисел бесконечен. Одной из самых больших загадок математики является расположение простых чисел в ряду всех натуральных чисел. Простые числа следуют одно за другим по закону, который еще не найден. Иногда два простых числа идут через одно (например, 17 и 19, 29 и 31), а иногда подряд идет миллион составных чисел. Сейчас ученые знают уже довольно много о том, сколько и какие простые числа содержатся среди натуральных чисел. Но остаётся ещё много неподтверждённых гипотез, несовершённых открытий в этой области исследований.

№ слайда 5 Для людей поиск простых чисел превратился в целенаправленный отбор отдельных
Описание слайда:

Для людей поиск простых чисел превратился в целенаправленный отбор отдельных представителей этого ряда. Один из рекордов поставил в своё время Эйлер, найдя простое число 231 − 1 = 2147483647. Наибольшим известным простым числом по состоянию на февраль 2011 года является 243112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS. Назначение простых чисел

№ слайда 6 За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичн
Описание слайда:

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр организация за свободу в интернете (EFF) назначила денежные призы соответственно в 150 000 и 250 000 долларов США. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр. Так зачем люди так настойчиво продолжают искать простые числа? Большие простые числа (порядка 10300) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел

№ слайда 7 Криптография - наука о способах преобразования (шифрования) информации с цель
Описание слайда:

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

№ слайда 8 Шифрование, защита информации актуальны в политике, экономике, бизнесе и про
Описание слайда:

Шифрование, защита информации актуальны в политике, экономике, бизнесе и прочих сферах человеческой деятельности, где востребованы системы безопасности с применением информационно-коммуникационных технологий. Простые числа интересуют также и военных, разведку и контрразведку. Знаменитая «Гипотеза Римана» была сформулирована немецким математиком Георгом Фридрихом Бернардом Риманом в 1859 году. Согласно ей, характер распределения простых чисел может существенно отличаться от предполагаемого в настоящее время.

№ слайда 9 Напомню, что математикам до сих пор не удавалось обнаружить какой-либо систем
Описание слайда:

Напомню, что математикам до сих пор не удавалось обнаружить какой-либо системы в характере распределения простых чисел. Так, считается, что в окрестности целого числа х среднее расстояние между последовательными простыми числами пропорционально логарифму х. Тем не менее, уже давно известны так называемые парные простые числа (простые числа-близнецы, разность между которыми равна 2: 11 и 13, 29 и 31, 59 и 61). Иногда они образуют целые скопления, например 101, 103, 107, 109 и 113. У математиков давно существовало подозрение, что такие скопления существуют и в области очень больших простых чисел, однако ни доказать, ни опровергнуть это утверждение до сих пор не удавалось.

№ слайда 10 Если такие «кластеры» будут найдены, стойкость криптографических ключей, исп
Описание слайда:

Если такие «кластеры» будут найдены, стойкость криптографических ключей, используемых в настоящее время, может в одночасье оказаться под очень большим вопросом. Это непосредственно относится и к сохранности информации в Интернете. Математическое сообщество в полной мере оценило важность задачи — гипотеза Римана была признана одной из 7 важнейших научных проблем тысячелетия. Институт математики Clay в США предложил $1 млн. за ее доказательство либо опровержение.

№ слайда 11 В поиске простых чисел весьма полезным оказался метод, восходящий еще к древн
Описание слайда:

В поиске простых чисел весьма полезным оказался метод, восходящий еще к древнегреческому ученому Эратосфену. Он жил в третьем веке до новой эры в Александрии. Эратосфен занимался самыми различными вопросами - ему принадлежат интересные исследования в области математики, астрономии и других наук. Впрочем, такая разносторонность привела его к некоторой поверхностности. Современники несколько иронически называли Эратосфена "во всем второй": второй математик после Евклида, второй астроном после Гиппарха и т.д. История алгоритма «Решето Эратосфена»

№ слайда 12 Эратосфен придумал для поиска простых чисел следующий способ: Сначала вычерки
Описание слайда:

Эратосфен придумал для поиска простых чисел следующий способ: Сначала вычеркивают все числа, делящиеся на 2 (исключая само число 2). Потом берут первое из оставшихся чисел (а именно 3). Ясно, что это число - простое. Вычеркивают все идущие после него числа, делящиеся на 3. Первым оставшимся числом будет 5. Вычеркивают все идущие после него числа, делящиеся на 5, и т.д. Числа, которые уцелеют после всех вычеркиваний, и являются простыми: 2, 3, 5, 7, 11, 13, …

№ слайда 13 В математике Эратосфена интересовал вопрос о том, как найти все простые числ
Описание слайда:

В математике Эратосфена интересовал вопрос о том, как найти все простые числа среди натуральных чисел от 1 до N (Эратосфен считал 1 простым числом). Это стало возможным путём поэтапного удаления (вычёркивания) из списка всех составных чисел. Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а «выкалывали» цифры, то табличка после описанного процесса напоминала решето. Поэтому метод Эратосфена для нахождения простых чисел получил название «решето Эратосфена».

№ слайда 14
Описание слайда:

№ слайда 15 В поисках истины Первый алгоритм поиска простых чисел, приходящий в голову, п
Описание слайда:

В поисках истины Первый алгоритм поиска простых чисел, приходящий в голову, примерно таков. Каждое число из интервала от 1 до N проверить на "простоту" по определению: оно должно делиться только на 1 и себя. Подсчитаем сколько раз оно делится нацело и получим ответ: … {Алгоритм 1} For I:=1 to N do begin K:=0; For J:=1 to I do If I mod J = 0 then K:=K+1; If K=2 then Writeln(‘ ‘,I); {в случае только двух делителей} end; …

№ слайда 16 Рассмотрим недостатки данного алгоритма: В Паскале по некоторым причинам резу
Описание слайда:

Рассмотрим недостатки данного алгоритма: В Паскале по некоторым причинам результат компиляции Inc(K), работает быстрее, чем K:=K+1. Нет смысла делить I на все числа, большие, чем половина I - все равно нацело не разделится. Кроме того, подсчёт количества делений сам по себе не нужен: любое удачное деление нацело на число, не равное 1 и самому себе свидетельствует о том, что число не является простым. Но самый главный недостаток алгоритма – большое количество итераций (повторений) цикла, примерно n*(n/2).

№ слайда 17 Суть дальнейшего и главного улучшения алгоритма вычисления множества простых
Описание слайда:

Суть дальнейшего и главного улучшения алгоритма вычисления множества простых чисел заключается в следующем: нет необходимости производить деления на составные числа, так как каждое составное число есть произведение простых его составляющих. Постепенно такого рода рассуждения приводят к наиболее оптимальному алгоритму поиска простых чисел как в небольшом, так и достаточно большом интервале. Огромную роль играют ограничения, накладываемые на алгоритм поиска. Если имеется ограничение по времени (что очень вероятно), то алгоритм Эратосфена с заданием справляется очень хорошо, особенно для больших чисел. Если имеется очень узкое ограничение по занимаемой памяти компьютера (очень маловероятно), то простая проверка перебором - достаточно удобный способ.

№ слайда 18 Варианты реализации алгоритма поиска простых чисел «Решето Эратосфена» В Паск
Описание слайда:

Варианты реализации алгоритма поиска простых чисел «Решето Эратосфена» В Паскале есть несколько способов оформить процесс вычеркивания чисел «решетом Эратосфена» с помощью структурированных типов: множество; массив; строки.

№ слайда 19 C помощью множества Множество целых чисел не превышает значения 255. Если чис
Описание слайда:

C помощью множества Множество целых чисел не превышает значения 255. Если число не простое - исключаем его из множества. Перед работой присваиваем множеству диапазон чисел от 2 до N: {Алгоритм 2} Var M:set of byte; i,k,N:byte; begin {ввод и инициализация} readln(N); M:=[2..N]; k:=2; {алгоритм решето Эратосфена} repeat for i:=k+1 to N do if (i in M) and (i mod k=0) then M:=M-[i]; inc(k); while (k<=N) and not (k in M) do inc(k); until k>N; {вывод ряда простых чисел} for i:=2 to N do if i in M then write(' ',i); readln; end.

№ слайда 20 C помощью массива Лучше использовать массив с элементами логического типа. Бу
Описание слайда:

C помощью массива Лучше использовать массив с элементами логического типа. Будем считать, что на i-ом месте массива P стоит true (или 1) если число простое, иначе false (или 0). Перед работой массив нужно "проинициализировать" значениями true (или 1), т.е. считаем, что все числа простые (как при доказательстве от противного): {Алгоритм 3} Var P:array [2..65535] of boolean; i,k,N:word; begin {ввод и инициализация} readln(N); fillchar(P,N,1); k:=2; {алгоритм решето Эратосфена} repeat for i:=k+1 to N do if P[i] and (i mod k=0) then P[i]:=false; inc(k); while (k<=N) and (not P[k]) do inc(k); until k>N; {вывод ряда простых чисел} for i:=2 to N do if P[i] then write(' ',i); readln; end.

№ слайда 21 C помощью строк Будем считать, что на i-ом месте строки S стоит &#039;*&#039; если числ
Описание слайда:

C помощью строк Будем считать, что на i-ом месте строки S стоит '*' если число простое, иначе ' ' (пробел). Перед работой со строкой нужно ее "инициализировать" символами '*', т.е. считаем, что все числа простые (как при доказательстве от противного). Кроме этого нужно знать, что строка содержит не более 255 символов (как сделать еще больше? Создать массив символов - это другой способ): {Алгоритм 4} Var S:string[255]; i,k,N:byte; begin {ввод и инициализация} readln(N); fillchar(S,N,'*'); S[1]:=' '; k:=2; {алгоритм решето Эратосфена} repeat for i:=k+1 to N do if (S[i]='*')and(i mod k=0) then S[i]:=' '; inc(k); while (k<=N) and(S[k]=' ') do inc(k); until k>N; {вывод ряда простых чисел} for i:=2 to N do if S[i]='*' then write(' ',i); readln; end.

№ слайда 22 На этих примерах видно, какие есть возможности у Паскаля для реализации алгор
Описание слайда:

На этих примерах видно, какие есть возможности у Паскаля для реализации алгоритма «Решето Эратосфена». Каждый алгоритм имеет свои ограничения на конечное число: 255 и 65535. Можно написать программу с использованием указателей на ячейку памяти при описании массива. Тогда ограничение для чисел здесь увеличивается до типа longint или comp. А если написать операцию проверки делимости для вещественных чисел, то ограничение для чисел увеличивается и для extended (самого большого числа). Но для вещественных чисел нужно менять цикл for на While, что может привести к увеличению времени работы алгоритма. Можно использовать для реализации алгоритма процедуры и функции. Возможностей улучшить характеристики алгоритма достаточно много, но это тема уже следующего, более углублённого, исследования.

№ слайда 23 http://ru.wikipedia.org/wiki/Простое_число http://ru.wikipedia.org/wiki/Решет
Описание слайда:

http://ru.wikipedia.org/wiki/Простое_число http://ru.wikipedia.org/wiki/Решето_Эратосфена http://www.intuit.ru/department/algorithms/algocombi/6/2.html http://dev.kurepin.com/texts/2.htm http://olymp-programming.blogspot.com/2011/03/blog-post_19.html http://www.bibliofond.ru/view.aspx?id=457401 http://progrm.ru/?p=230 http://garshin.ru/evolution/mathematics/math-problems.html Спасибо за внимание! Ссылки на Интернет-ресурсы:

Краткое описание документа:

Исследование в криптографии на тему прикладного применения простых чисел. Приведены различные варианты реализации алгоритма "Решето Эратосфена" на языке программирования Паскаль.

Сейчас ученые знают уже довольно много о том, сколько простых чисел содержится среди натуральных чисел. Но остаётся ещё много неподтверждённых гипотез, не совершённых открытий в этой области исследований.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр организация за свободу в интернете (EFF) назначила денежные призы соответственно в 150 000 и 250 000 долларов США. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр. Зачем людям нужны такие исследования? Разбирёмся.

Автор
Дата добавления 06.05.2016
Раздел Информатика
Подраздел Презентации
Просмотров129
Номер материала ДБ-069941
Получить свидетельство о публикации
Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх