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

Новгорода Иванцова Светлана Анатольевна

2016 г.

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

алгоритма

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.

Назначение простых чисел

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;
…

работает быстрее, чем K:=K+1.
Нет смысла делить I на все числа, большие, чем половина I - все равно нацело не разделится.
Кроме того, подсчёт количества делений сам по себе не нужен: любое удачное деление нацело на число, не равное 1 и самому себе свидетельствует о том, что число не является простым.

Но самый главный недостаток алгоритма – большое количество итераций (повторений) цикла, примерно n*(n/2).

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

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

несколько способов оформить процесс вычеркивания чисел «решетом Эратосфена» с помощью структурированных типов:

множество;
массив;
строки.

не простое - исключаем его из множества. Перед работой присваиваем множеству диапазон чисел от 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.

что на 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.

'*' если число простое, иначе ' ' (пробел). Перед работой со строкой нужно ее "инициализировать" символами '*', т.е. считаем, что все числа простые (как при доказательстве от противного). Кроме этого нужно знать, что строка содержит не более 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, что может привести к увеличению времени работы алгоритма.
Можно использовать для реализации алгоритма процедуры и функции. Возможностей улучшить характеристики алгоритма достаточно много, но это тема уже следующего, более углублённого, исследования.