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

Автор проекта: учитель информатики и ИКТ МБОУ «Школа №58» г. Нижнего НовгородаИванцова Светлана Анатольевна2016 г. Простые числа в криптографии. Волшебное решето Эратосфена. Справка: простое число -… Назначениепростыхчисел Алгоритм Эратосфена 1 2 3 Вариант строки 9 Почему решето? 4 Демонстрация алгоритма 5 В поисках истины 6 Вариант множество 7 Вариант массив 8 Перспективы исследования 10 Справка о предмете исследования Просто́е число́ — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Число 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, … Более двух тысяч лет назад великий древнегреческий математик Евклид доказал, что ряд простых чисел бесконечен. Одной из самых больших загадок математики является расположение простых чисел в ряду всех натуральных чисел. Простые числа следуют одно за другим по закону, который еще не найден. Иногда два простых числа идут через одно (например, 17 и 19, 29 и 31), а иногда подряд идет миллион составных чисел. Сейчас ученые знают уже довольно много о том, сколько и какие простые числа содержатся среди натуральных чисел. Но остаётся ещё много неподтверждённых гипотез, несовершённых открытий в этой области исследований. Для людей поиск простых чисел превратился в целенаправленный отбор отдельных представителей этого ряда. Один из рекордов поставил в своё время Эйлер, найдя простое число 231 − 1 = 2147483647.Наибольшим известным простым числом по состоянию на февраль 2011 года является 243112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS. Назначение простых чисел За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр организация за свободу в интернете (EFF) назначила денежные призы соответственно в 150 000 и 250 000 долларов США. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.Так зачем люди так настойчиво продолжают искать простые числа? Большие простые числа (порядка 10300) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел Криптография - наука о способах преобразования (шифрования) информации с целью ее защиты от незаконных пользователей (разработка шифров). Все используемые сегодня криптосистемы (с открытым ключом) опираются на алгоритмы разложения больших чисел на простые множители, работы с простыми числами. Таким образом, простые числа являются одной из неотъемлемых частей современных асимметричных криптосистем, то есть систем, использующих два ключа: открытый и секретный. Для того, чтобы криптосистема была стойкой к вскрытию, в ней необходимо использовать простые числа большой длины (и выше). Для того, чтобы использовать большие простые числа, их необходимо сначала построить. Шифрование, защита информации актуальны в политике, экономике, бизнесе и прочих сферах человеческой деятельности, где востребованы системы безопасности с применением информационно-коммуникационных технологий.Простые числа интересуют также и военных, разведку и контрразведку. Знаменитая «Гипотеза Римана» была сформулирована немецким математиком Георгом Фридрихом Бернардом Риманом в 1859 году. Согласно ей, характер распределения простых чисел может существенно отличаться от предполагаемого в настоящее время. Напомню, что математикам до сих пор не удавалось обнаружить какой-либо системы в характере распределения простых чисел. Так, считается, что в окрестности целого числа х среднее расстояние между последовательными простыми числами пропорционально логарифму х. Тем не менее, уже давно известны так называемые парные простые числа (простые числа-близнецы, разность между которыми равна 2: 11 и 13, 29 и 31, 59 и 61). Иногда они образуют целые скопления, например 101, 103, 107, 109 и 113. У математиков давно существовало подозрение, что такие скопления существуют и в области очень больших простых чисел, однако ни доказать, ни опровергнуть это утверждение до сих пор не удавалось. Если такие «кластеры» будут найдены, стойкость криптографических ключей, используемых в настоящее время, может в одночасье оказаться под очень большим вопросом. Это непосредственно относится и к сохранности информации в Интернете.Математическое сообщество в полной мере оценило важность задачи — гипотеза Римана была признана одной из 7 важнейших научных проблем тысячелетия. Институт математики Clay в США предложил $1 млн. за ее доказательство либо опровержение. В поиске простых чисел весьма полезным оказался метод, восходящий еще к древнегреческому ученому Эратосфену. Он жил в третьем веке до новой эры в Александрии.Эратосфен занимался самыми различными вопросами - ему принадлежат интересные исследования в области математики, астрономии и других наук. Впрочем, такая разносторонность привела его к некоторой поверхностности. Современники несколько иронически называли Эратосфена "во всем второй": второй математик после Евклида, второй астроном после Гиппарха и т.д. История алгоритма«Решето Эратосфена» Эратосфен придумал для поиска простых чисел следующий способ:Сначала вычеркивают все числа, делящиеся на 2 (исключая само число 2). Потом берут первое из оставшихся чисел (а именно 3). Ясно, что это число - простое. Вычеркивают все идущие после него числа, делящиеся на 3. Первым оставшимся числом будет 5. Вычеркивают все идущие после него числа, делящиеся на 5, и т.д. Числа, которые уцелеют после всех вычеркиваний, и являются простыми: 2, 3, 5, 7, 11, 13, … В математике Эратосфена интересовал вопрос о том, как найти все простые числа среди натуральных чисел от 1 до N (Эратосфен считал 1 простым числом). Это стало возможным путём поэтапного удаления (вычёркивания) из списка всех составных чисел.Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а «выкалывали» цифры, то табличка после описанного процесса напоминала решето. Поэтому метод Эратосфена для нахождения простых чисел получил название «решето Эратосфена». В поисках истины Первый алгоритм поиска простых чисел, приходящий в голову, примерно таков. Каждое число из интервала от 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;… Рассмотрим недостатки данного алгоритма:В Паскале по некоторым причинам результат компиляции Inc(K), работает быстрее, чем K:=K+1. Нет смысла делить I на все числа, большие, чем половина I - все равно нацело не разделится. Кроме того, подсчёт количества делений сам по себе не нужен: любое удачное деление нацело на число, не равное 1 и самому себе свидетельствует о том, что число не является простым. Но самый главный недостаток алгоритма – большое количество итераций (повторений) цикла, примерно n*(n/2). Суть дальнейшего и главного улучшения алгоритма вычисления множества простых чисел заключается в следующем: нет необходимости производить деления на составные числа, так как каждое составное число есть произведение простых его составляющих.Постепенно такого рода рассуждения приводят к наиболее оптимальному алгоритму поиска простых чисел как в небольшом, так и достаточно большом интервале. Огромную роль играют ограничения, накладываемые на алгоритм поиска. Если имеется ограничение по времени (что очень вероятно), то алгоритм Эратосфена с заданием справляется очень хорошо, особенно для больших чисел. Если имеется очень узкое ограничение по занимаемой памяти компьютера (очень маловероятно), то простая проверка перебором - достаточно удобный способ. Варианты реализации алгоритма поиска простых чисел «Решето Эратосфена» В Паскале есть несколько способов оформить процесс вычеркивания чисел «решетом Эратосфена» с помощью структурированных типов:множество;массив;строки. 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. 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. 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. На этих примерах видно, какие есть возможности у Паскаля для реализации алгоритма «Решето Эратосфена». Каждый алгоритм имеет свои ограничения на конечное число: 255 и 65535. Можно написать программу с использованием указателей на ячейку памяти при описании массива. Тогда ограничение для чисел здесь увеличивается до типа longint или comp. А если написать операцию проверки делимости для вещественных чисел, то ограничение для чисел увеличивается и для extended (самого большого числа). Но для вещественных чисел нужно менять цикл for на While, что может привести к увеличению времени работы алгоритма. Можно использовать для реализации алгоритма процедуры и функции. Возможностей улучшить характеристики алгоритма достаточно много, но это тема уже следующего, более углублённого, исследования. http://ru.wikipedia.org/wiki/Простое_числоhttp://ru.wikipedia.org/wiki/Решето_Эратосфенаhttp://www.intuit.ru/department/algorithms/algocombi/6/2.htmlhttp://dev.kurepin.com/texts/2.htmhttp://olymp-programming.blogspot.com/2011/03/blog-post_19.htmlhttp://www.bibliofond.ru/view.aspx?id=457401 http://progrm.ru/?p=230 http://garshin.ru/evolution/mathematics/math-problems.html Спасибо за внимание! Ссылки на Интернет-ресурсы: