Проект по алгебре "Простые числа" ( 7 класс)

Выполнила: ученица 7 класса

Анастасия Калентьева

Руководитель: учитель математики

Калентьева Искра Алексеевна

                                        Всякий, кто изучает простые числа, бывает очарован и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые сомножители - такое естественное действие. Почему же простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?

         Ч. Узерелл «Этюды для программистов».

«Ни одному другому разделу теории чисел не свойственно столько загадочности и изящества, как разделу, занимающемуся изучением простых чисел - непокорных упрямцев, упорно не желающих делиться ни на какие числа, кроме единицы и самих себя. Некоторые задачи, относящиеся к теории распределения простых чисел, формулируются настолько просто, что понять их может и ребёнок. Тем не менее они настолько глубоки и далеки от своего решения, что многие математики считают их вообще не разрешимыми. Может быть, в теории чисел так же как и в квантовой механике, действует своё собственное соотношение неопределённости и в некоторых её разделах имеет смысл говорить лишь о вероятности того или иного результата?"

Мартин Гарднер  "Математические досуги"

Содержание

I. Введение. ……………………………………………………………

II. Основная часть. ……………………………………………............

1.      Понятие простого.

2.      Простые числа.

3.      Числа – близнецы

4.      Из истории простых чисел.

5.      Бесконечность ряда простых чисел.

6.      Формулы для нахождения простых чисел.

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

8.      Свойства простых чисел

9.      Применение простых чисел в криптографии.

10.   Простые числа в природе.

III. Практическая часть………………………………………………..

IV. Заключение ………………………………………………………………………………...

V. Литература……………………………………………………………………………………..

Цель работы: изучение истории простых чисел и исследование некоторых свойств и видов простых чисел.

Для достижения этой цели я поставила следующие задачи:

•✓ подобрать литературу по этой теме и изучить исторические сведения о простых числах;

•✓ понять принцип выделения простых чисел из натурального ряда, используя метод «Решето Эратосфена»;

•✓ выяснить, существует ли математическая формула для отыскания простых чисел;

•✓ выяснить, существует ли самое большое простое число;

•✓ познакомиться с закономерностями и свойствами простых чисел

•✓ исследовать современное состояние изучаемого вопроса.

I.Введение.

  Тема «Числа» меня заинтересовала ещё в 5 классе, тогда я работала над проектом   «Числа вокруг нас», и я решила продолжить  работу с числами в последующих классах.

Большинство чисел отличаются «хорошим поведением», например, четные числа чередуются с нечетными, каждое третье число всегда кратно трем, квадраты чисел подчиняются определенному закону. Можно составить длинный ряд чисел, которые ведут себя, как им положено, независимо от длины этого ряда и величины самих чисел.

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

С понятием «простого числа» Любовь Владимировна познакомила нас ещё в 6 классе. Тогда мне показалось: чтобы понять, что такое простое число, нужно лишь уметь считать и владеть четырьмя основными арифметическими действиями, но работая над проектом «Тайны простых чисел», удостоверилась в том, что простые числа были и продолжают оставаться одной из самых удивительных проблем в истории науки.   

Я решила узнать тайны простых чисел – историю их возникновения, сколько их, как они распределены в натуральном ряду, найдено ли самое большое простое число и т. д.

Таблица простых чисел до 997

2	79	191	311	439	577	709	857
3	83	193	313	443	587	719	859
5	89	197	317	449	593	727	863
7	97	199	331	457	599	733	877
11	101	211	337	461	601	739	881
13	103	223	347	463	607	743	883
17	107	227	349	467	613	751	887
19	109	229	353	479	617	757	907
23	113	233	359	487	619	761	911
29	127	239	367	491	631	769	919
31	131	241	373	499	641	773	929
37	137	251	379	503	643	787	937
41	139	257	383	509	647	797	941
43	149	263	389	521	653	809	947
47	151	269	397	523	659	811	953
53	157	271	401	541	661	821	963
59	163	277	409	547	673	823	971
61	167	281	419	557	677	827	977
67	173	283	421	563	683	829	983
71	179	293	431	569	691	839	991
73	181	307	433	571	701	853	997

II.Основная часть

1.Понятие простого

Слово «простой» в толковом словаре русского языка С.И.Ожегова обозначает «однородный по составу, не составной, не сложный, не трудный, легкодоступный пониманию, осуществлению». В энциклопедии «Вики словарь» значение слова «простой»: доступный и не требующий много времени и усилий для понимания, решения, выполнения, описания, использования; ничем не выделяющийся среди прочих, обыкновенный, типичный, стандартный; недорогой, без дополнительных функций, опций, аксессуаров, дополнительных этапов при производстве, ингредиентов и специй.

2.Простые числа

 Простые числа – это натуральные числа, которые делятся без остатка только на единицу и самое себя. Кстати, если натуральное число делится, кроме выше перечисленных, еще на какое-либо число, то оно именуется составным. Одна из самых знаменитых теорем гласит, что любое составное число может быть представлено в виде единственно возможного произведения простых чисел.

12=2х2х3      20=2х2х5

Процесс разложения числа на множители называется факторизацией: от латинского слова  facere- «делать» или «производить», именно этот процесс привел нас к точному определению простого числа, при факторизации которого мы получаем только единицу и само число в качестве множителей. Например, число 13 будет разложено так:

13=1х13

Несколько любопытных фактов.

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

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

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

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

3.Числа-близнецы.

Среди простых чисел встречаются так называемые "близнецы" или пары простых чисел, разница между которыми составляет двойку (например, 11 и 13). Именно эти пары чисел в таблице учебника выделены другим цветом. "Близнецы" появляются с некой периодичностью, причем, чем больше числа, тем реже они встречаются (11 и 13; 17 и 19; 29 и 31; 41 и 43; 59 и 61). То же происходит и с обычными простыми числами. В числах, близких к триллиону, лишь каждое 28 число является простым. Еще Евклидом было доказано, что простых чисел бесконечно много. Однако окончательного ответа на вопрос, конечно или бесконечно множество "близнецов", пока не существует

      Первые простые числа-близнецы:

  (3,  5),    (5,  7),    (11, 13),   (17, 19),   (29, 31),   (41, 43),   (59, 61),

  (71,  73),  (101, 103), (107, 109), (137, 139), (149, 151), (179, 181), (191, 193), (197, 199), (227, 229), (239, 241), (269, 271), (281, 283), (311, 313), (347, 349), (419, 421), (431, 433), (461, 463), (521, 523), (569, 571), (599, 601), (617, 619), (641, 643), (659, 661), (809, 811), (821, 823), (827, 829), (857, 859), (881, 883).

Простые числа-близнецы по мере увеличения встречаются в ряду натуральных чисел все реже. Однако компьютерные вычисления показывают, что парные числа продолжают встречаться даже среди необыкновенно больших чисел. А так как существует бесконечное количество простых чисел, можно выдвинуть гипотезу о существовании бесконечного числа чисел-близнецов, но это еще никому не удалось доказать.

Еще одна замечательная группа простых чисел, которая встречается в первой сотне натурального ряда, содержит три числа: 3,5 и 7. Они могут быть записаны в виде как       (р, р+2,р+4), где р – простое число. Эта группа простых чисел состоит из так называемых «троек». На самом деле существует только одна такая тройка. Это доказанный результат.

Самыми большими известными числами-близнецами (открытыми в 2011г) являются числа

3756801695685 · 2^666669 ± 1

 Каждое из которых состоит из 200700 цифр!

4. Из истории простых чисел.

Интерес к простым числам проявляли ещё математики Древней Греции. Они были знакомы с некоторыми свойствами простых чисел, располагали простейшими алгоритмами их поиска и, безусловно, видели их математическую красоту.

Поиск простых чисел всегда был сложной задачей. Один из первых известных методов приписывают Эратосфену из Кирены (273–194 до н. э.), древнегреческому математику, астроному и географу, который также заведовал Александрийской библиотекой.

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

Эратосфен записывал свою таблицу на папирусе, натянутом на рамку, и составные числа прокалывал. Получилось своеобразное сито, через которое составные числа просеивались, а простые оставались. Поэтому таблицу и сам способ назвали «Решетом Эратосфена».

 Давайте посмотрим, как с помощью этого метода можно найти простые числа в первой сотне натуральных чисел.

Во-первых, составим таблицу со всеми натуральными числами от 1 до 100. Затем вычеркнем все числа, кратные двум: 4, 6, 8, 10 потом вычеркнем все числа, кратные трем: 6 (уже вычеркнули), 9, 12, 15. Затем проделаем то же самое для чисел, кратных пяти и семи.

Остались только простые числа.

Обратите внимание, что «просеивание» закончилось на числе 10, квадратном корне из 100. В общем случае, чтобы найти все простые числа, меньшие, чем заданное число N, нужно «просеять» все числа, которые меньше или равны квадратному корню из N. Это и дает метод нахождения простых чисел, который используется и сегодня, спустя более чем 2000 лет после изобретения, для поиска «малых простых чисел»: так называются простые числа, которые меньше 10 млрд.

5. Бесконечность ряда простых чисел.

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

С первого взгляда видно, что простые числа совершенно непредсказуемы. Например, между 1 и 100 простых чисел больше, чем между 101 и 200. Всего в первой тысяче 168 простых чисел. Можно предположить, что если продолжить нашу таблицу, то с каждой тысячей количество простых чисел будет увеличиваться. Но это не так. Уже известно, что, например, среди тысячи чисел между 10100 и 10100 + 1000 находится лишь два простых числа. И эти числа состоят более чем из ста цифр!

 Поэтому возникает вопросов: существует ли последнее простое число в ряду натуральных чисел, т. е. имеет ли ряд простых чисел конец?

Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20) около 300 лет до нашей эры. Он доказал, что за каждым простым числом имеется ещё большее простое число, т. е. существует бесчисленное множество простых чисел. 

 Он рассуждал так.

Возьмем ряд последовательных простых чисел, например: 2,3,5.

Затем перемножим их: 2х3х5=30.

Теперь добавим к результату единицу: 2х3х5+1=30+1=31.

Ясно, что если разделить 31 на любое простое число из этого ряда-2,3,5,-то в остатке получится 1:

31/2=15+1

31/3=10+1

31/5=6+1

Это означает, что число 31 не делится на выбранные простые числа. , Это справедливо и в общем случае: если взять ряд последовательных простых чисел, перемножить их и добавить единицу, то полученное число не будет делиться ни на одно из исходных простых чисел. Этот простой факт и лежит в основе доказательства Евклида.

Число 31 тоже простое число, но его нет в первоначальном списке, который, следовательно, является неполным.

 Возьмем следующий ряд чисел в качестве примера: (2, 3, 5, 7, 11, 13).

Перемножим их и добавим единицу:

2 х 3 х 5 х 7 х 11 х 13 + 1 = 30 030 + 1 = 30 031.

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

30 031 = 59 х 509.

Евклид уже доказал, что любое натуральное число может быть единственным образом разложено в произведение простых множителей. В случае с числом 30 031, которое является составным числом, ясно, что для его разложения в произведение простых множителей чисел в списке (2, 3, 5, 7, 11, 13) будет недостаточно, то есть этот список неполон.

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

1) простое число, которого нет в списке;

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

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

К сожалению, этот метод не позволяет найти все простые числа, хотя он является важной отправной точкой. Можно было бы подумать, что не так уж важно доказывать, что множество простых чисел бесконечно, ибо это подсказывает нам интуиция. Однако с простыми числами нужно быть очень осторожными, ведь они настолько «редко» встречаются, как будто могут закончиться в любой момент. Тем не менее, теорема Евклида убедительно доказывает, что этого не произойдет.

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

7. Формулы для нахождения простых чисел.

Еще в глубокой древности ученых интересовал вопрос о том, по какому закону расположены в натуральном ряду простые числа.  Долгое время математики искали формулу, по которой можно было бы найти все простые числа. Леонард Эйлер указал на формулу P = n^2 – n + 41. В ходе проверки выяснилось, при всех целых значениях n от 0 до 40 она даёт простые числа.

n = 1, Р = 1^2 – 1 + 41 = 41;

n = 3, Р = 3^2 – 3 + 41 = 47;

n = 12, Р = 12^2 – 12 + 41 = 173;

n = 21, Р = 21^2 – 21 + 41 = 461;

n = 35, Р = 35^2 – 35 + 41 = 1231;

Однако при n = 41 формула перестаёт «работать». 2 147 483 647 - самое большое простое число, которое в своё время нашел Эйлер. 

   Французский монах  Марен Мерсенн (1588–1648 годы) обратил внимание на числа особого вида: 2^1 – 1 = 1; 2^2 – 1 = 3; 2^3 – 1 = 7;  2^4 – 1 = 15,…. и заинтересовался распределением простых и составных чисел в этой последовательности. С тех пор числа вида    Мр = 2^p – 1, где p – другое простое число, называются числами Мерсенна.

В 1770 г. Немецкий математик Иоганн Генрих Ламберт опубликовал таблицу наименьших делителей всех чисел, не превосходящих 102000 и не делящихся на 2, 3, 5. Вложив в этот труд поистине колоссальные усилия, Ламберт гарантировал бессмертие тому, кто доведет таблицу делителей до миллиона. На его призыв откликнулись многие вычислители.

К середине 19 века уже были составлены таблицы наименьших делителей не только первого миллиона, но и следующих, в плоть до 9. В это же время в прессе появились сообщения, которые представлялись абсолютно фантастическими: в Венскую академию поступило 7 больших томов рукописных таблиц “Великий канон делителей всех чисел,

которые не делятся на 2, 3 и 5, и простых чисел между ними до 100330201”. Автором этого труда был Якуб Филипп Кулик, профессор высшей математики Пражского университета.

Некоторые представления о распределения простых чисел имели уже древние греки. Из доказательства Евклида следует, например, что они не собраны вместе, а разбросаны по всей числовой оси. Но как часто?

В 1845 г французский математик Жозеф Бертан, исследуя таблицу простых чисел в промежутке от 1 до 6000000, обнаружил, что между числами nи n2 – 2, где n> 3, содержится по крайней мере одно простое число. В последствии это свойство получило название постулата Бертрана, хотя самому Бертану обосновать его так и не удалось. Доказал его в 1852 г русский математик Пафнутий Львович Чебышев. Из результата Чебышева следовала и более точная оценка. Таким образом, даже среди очень больших чисел простые числа не так уж редки.

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

Вернемся к гипотезе Мерсенна, помните, он предположил, что двойка в степенях 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, уменьшенная на единицу, обязательно даст в результате простое число. Все остальные числа, рассчитанные по этой формуле, будут составными. Почему он так решил – непонятно. Мерсенн и сам не настаивал на своей гипотезе. Однако после его смерти она стала необычайно популярна. С тех пор простые числа такого вида стали называться числами Мерсенна, а его формула – популярной для определения новых больших простых чисел. Числа Мерсенна встречаются очень редко, и пока неизвестно, есть ли какая-то зависимость между номером числа Мерсенна и его величиной. Если такая зависимость есть, она заметно ускорит поиск новых больших простых чисел. Но главной загадкой по-прежнему остается вопрос, конечен ли ряд чисел Мерсенна.

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

Эпоха компьютерных технологий вернула интерес к поиску большого простого числа. Двое американских школьников – Лаура Никел и Лэндон Нолл -  в конце 70-х обнаружили 25-е простое число Мерсенна, используя мощный по тем временам компьютер. Степень, в которую надо было возвести двойку, оказалась равна 21 701. На тот момент это было самое большое простое число. Впрочем, чуть позже Нолл уже в одиночку открыл и следующее, 26-е число.

Успех школьников подтвердил, что в компьютерную эпоху добывать простые числа могут не только великие математики.
С этого момента охотиться за большими простыми числами принялись не только профессионалы, но и энтузиасты. В 1995 году был создан специальный проект распределенных вычислений GIMPS (Great Internet Mersenne Prime Search), к которому может подключиться любой желающий. Для этого достаточно бесплатно скачать на свой компьютер программу с сайта GIMPS. Таких добровольцев сегодня тысячи. По большей части «охотниками» движет спортивный интерес, но если вдруг новое число будет обнаружено, автора ждет слава и приз в три тысячи долларов.

В декабре прошлого года 51-летний Джонатан Пейс, инженер-электромеханик из американского штата Теннесси обнаружил 50-е простое число из ряда так называемых чисел Мерсенна. Новое простое число в десятичной записи содержит 23 249 425 цифр. Заметим, что в романе «Война и мир» всего около 3,1 миллиона символов. Число, открытое Пейсом, составляет примерно восемь таких романов.

Профессор И.К. Андронов в книге «Арифметика натуральных чисел» приводит рассказ о воображаемом путешествии по бесконечной дороге простых чисел: «Мысленно возьмем прямо линейный провод, выходящий из классной комнаты в мировое пространство, пробивающий земную атмосферу, уходящий туда, где Луна совершает вращение, и далее за огненный шар Солнце, в мировую бесконечность.

Мысленно подвесим на провод через каждый метр электрические лампочки, нумеруя их, начиная с ближней:1,2,3,…,1 000,…,1 000 000,…, включим ток с таким расчетом, чтобы загорелись все лампочки с простыми номерами, и полетим вблизи провода».

Вместе с автором этой книги мы начинаем движение с первой электрической лампочки, которая не осветила нам старта; она не горит, так как ее номер (единица) не является простым числом. Сразу за ней две лампочки с номерами 2 и 3 включены, эти числа простые. Оставим позади горящие лампочки 5 и 7. Они пронумерованы простыми числами. На нашем длинном пути очень редко будут попадаться числа-близнецы. Вот промелькнули следующие числа-близнецы: 11 и 13, 17 и 19. Мы быстро набираем скорость; оставляя позади лампочки 101 и 103, 827 и 829; теперь реже и реже встречаются освещенные островки из лампочек, пронумерованы простыми числами-близнецами. Вот на фоне темноты и мрака засверкали лампочки с номерами 10 016 957 и 10 016 959; это

последняя пара известных простых чисел-близнецов. Возможно, где то в бесконечных

просторах обрадуют наш взор еще пара светящихся лампочек, или такие близнецы исчезнут на всегда. Нам встречаются участки, довольно часто освещаемые лампочками, но чаще путь проходит в темноте. Из первого миллиона промелькнуло всего 78 498 горящих лампочек, 921 502 не горели.

Однако мы только начали движение, они еще встретятся, но в какой миг? Закономерности нет.

8.Свойства простых чисел. 

Простые числа - простой математический объект, но загадок они доставили математикам немало и многие ещё не разгаданы.

•✓ Если присмотреться к ряду простых чисел 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,……, то можно отметить, что все они, кроме 2, нечетные.

•✓ 168 мест первой тысячи натуральных чисел занимают простые числа. Из  них 16 чисел палиндромические, каждое равно обращённому: 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929.

Некоторые простые числа находят симметричное себе простое число:

4 пары двузначных 13 – 31, 17 – 71, 37 – 73, 79 – 97; 14 пар трёхзначных чисел 107 – 701, 113 – 311, 149 – 941, 157 – 751, 167 – 761, 179 – 971, 199 – 991, 337– 733, 347 – 743, 359 – 953, 389 – 983, 709 – 907, 739 – 937, 769 – 967.

•✓ Пары чисел, которые отличаются на 2, как 3 и 5, 5 и 7, 11 и 13, 17 и 19, 41 и 43, 59 и 61, 71 и 73 и т. д., получили образное название «близнецы». Их ещё называют парными простыми числами. Если внимательно к ним присмотреться, то можно заметить, что сумма чисел каждой пары (исключение составляет пара 3;5) всегда кратна трем. Более того, при делении на тройку левого собрата в остатке всегда остается двойка, а правого – единица. Все пары простых близнецов, кроме 3 и 5, имеют вид 6n ± 1. Сейчас с помощью мощных компьютеров вычислены миллиарды простых чисел. На данный момент самыми

большими «близнецами» являются 3756801695685 • 2^666669 –  1 и 3756801695685 • 2^666669 +  1, которые были обнаружены 24 декабря 2011 года.

Для записи каждого из этих чисел понадобится 200700цифр. По мере удаления от нуля «близнецов» становится всё меньше. Так, в первой сотне натуральных чисел насчитывается восемь пар чисел – близнецов, а в пределах пяти сотен (с 9501 по 1000) – шесть. Но до сих пор неизвестно, конечно или бесконечно количество пар близнецов.  Нет пока ответа на вопрос о том, существует ли самая большая пара чисел - близнецов.

•✓ Простые числа распределены очень прихотливо: между числами - близнецами стоит всего одно число, но можно указать такие простые числа, между которыми стоит миллион чисел, все из которых составные. Однако знаменитый русский математик П. Л. Чебышев в 1852 г. доказал, что между натуральным числом n и  вдвое большим числом (2n)  имеется всегда хотя бы одно простое число.  Например: 3 и 6 - между ними находится простое число 5; между 10 и 20 находятся 11, 13, 17, 19  и т. д.   Это утверждение впервые высказал французский математик Ж. Бертран, но доказать его не смог.

•✓ Сумма двух простых чисел может быть простым числом: 2 + 3 = 5; 2 + 11 = 13 и др., но при условии, что одно из этих чисел будет равно 2, иначе сумма двух нечётных чисел будет чётным числом, следовательно, делится на 2 и не является простым.

•✓ Сумма двух последовательных натуральных чисел может оказаться простым числом: 2 + 3 = 5; 3 + 4 = 7; 5 + 6 = 11; 6 + 7 = 13; 8 + 9 = 17 и т. д., а сумма трёх последовательных натуральных чисел не может быть простым числом  (2 + 3 + 4 = 9, 5 + 6 + 7 = 18,  каждый раз получается составное число)

•✓ Ещё одну закономерность, не разгаданную по сей день, открыл в 1742 году российский академик Х. Гольдбах. Он заметил, что любое чётное число, большее 2, можно представить в виде сумму двух простых чисел: 4 = 2 + 2; 8 = 3 + 5 и т. д., а любое нечётное число, большее 5 – в виде суммы трёх простых чисел: 7 = 2 + 2 + 3; 11 = 3 + 3 + 5. Полностью это утверждение не доказано и  не опровергнуто до сих пор. То, что это утверждение выполняется для всех очень больших нечётных чисел, доказал академик И. М. Виноградов в 1938 году.

9. Применение простых чисел в криптографии.

Поиск простых чисел — по крайней мере больших простых чисел — довольно сложная задача, потому что еще никому не удалось найти формулу или алгоритм, позволяющий генерировать любые простые числа. Но может возникнуть логичный вопрос: «Для чего нужны простые числа?»

На этот вопрос можно дать два ответа. Первый из них имеет теоретическое значение. Попытки вычисления простых чисел ведут к появлению новых интересных инструментов для расчетов, особенно для компьютерных вычислений. Кроме того, наличие большого списка простых чисел позволяет проверять теоремы, которые еще не доказаны. Если кто-то выдвигает гипотезу относительно простых чисел, но оказывается, что одно из миллионов чисел нарушает ее, то вопрос снимается. Это стимулирует поиск простых чисел различных видов: простых чисел Мерсенна, чисел-близнецов и так далее. Иногда такой поиск превращается в соревнование, в котором устанавливаются мировые рекорды и за победы присуждаются большие призы.

Но есть и другая, более практическая причина, связанная с так называемым шифрованием. Электронная почта, банковские операции, кредитные карты и мобильная телефонная связь — все это защищено секретными кодами, непосредственно основанными на свойствах простых чисел.

Простые числа являются не только объектом пристального изучения математиками всего мира, но уже давно и успешно используются. Наиболее распространенным примером использования простых чисел является применение их в криптографии (шифровании данных). Самые безопасные и трудно дешифруемые методы криптографии основаны на применении простых чисел, имеющих в составе более трех сотен цифр.

В 1975 г. Уитфилду Диффи и Мартину Хеллману, в то время работавшим в Стэнфордском университете, пришла в голову идея асимметричного шифрования, или «шифрования с открытым ключом». Эта система основана на специальных математических функциях, называемых «односторонними функциями с потайным входом», которые позволяют зашифровывать текст, но делают расшифровку практически невозможной без знания используемого кода. Идея состоит в том, что каждый пользователь имеет пару ключей: открытый и закрытый. Если мы хотим отправить кому-то сообщение, мы зашифровываем это сообщение с помощью открытого ключа — то есть ключа, известного всем. Но только человек, имеющий соответствующий закрытый ключ, может расшифровать это сообщение. Одним из преимуществ такого метода является то, что закрытый ключ никогда не передается и поэтому его не нужно постоянно менять в целях безопасности. Идея метода не совсем проста, но мы можем пояснить ее с помощью аналогии. Представьте себе большой магазин, где продаются сотни тысяч банок с краской разного цвета. Возьмем две любые банки и смешаем краску в разных количествах. Пока все просто. Теперь, если мы покажем кому-нибудь получившийся цвет и попросим «расшифровать», какое количество каких красок использовалось изначально, на такой вопрос будет очень трудно ответить.

Именно так работают односторонние функции с потайным входом, которые легко применить в одном направлении, но практически невозможно — в обратном.

Схема, иллюстрирующая алгоритм Диффи — Хеллмана. Имеются два абонента, Алиса и Боб, желающие общаться втайне. Они открыто договариваются о двух числах (простое число р и другое число g, имеющие определенные свойства). И Алиса, и Боб выполняют некоторые операции с этими числами и с еще одним целым числом, которое они держат в секрете, а затем открыто посылают друг другу результаты. Теперь и Алиса, и Боб выполняют с полученным результатом еще одну операцию и получают один и тот же ответ, который будет для них секретным кодом. Потенциальный шпион, перехвативший результаты, посланные Алисой и Бобом, не может сгенерировать секретный код, имея лишь эту информацию.

Предположим теперь, что вместо банок с краской в магазине находятся простые числа. Возьмем любые два, например, 7 и 13, и перемножим их (аналогично смешиванию краски). В результате мы получим 7 х 13 = 91.

Тогда возникает вопрос: можно ли узнать, какие простые числа были перемножены, чтобы в результате получилось 91? Для ответа на него надо взять список простых чисел и проделать несколько проверок. Казалось бы, простое решение, как и в случае определения цвета красок, если в магазине было всего около десятка основных цветов.

Но с простыми числами все намного сложнее.

Например, ни у кого не хватит терпения проверить, что число 1409 305 684 859 является результатом умножения простых чисел 705 967 и 1996 277, особенно если учесть, что эти два простых числа взяты из списка простых чисел между 1 и 2000000, а там таких «всего лишь» 148933. Однако мы живем в эпоху высоких технологий, и, конечно, эту задачу можно довольно быстро решить с помощью хорошей программы и мощного компьютера. Хотя все зависит от того, насколько большой этот магазин красок. Не следует также забывать, что количество простых чисел не просто очень большое, а бесконечное.

Пара простых чисел в приведенном выше примере содержит лишь несколько цифр. Если мы возьмем простые числа, каждое из которых содержит сотни цифр, то время, которое потребуется компьютерной программе на простой перебор всех возможных вариантов — метод «грубой силы», как говорят криптографы, — будет больше, чем предполагаемое время существования Земли.

Простые числа повсеместно используются в нашей повседневной жизни, например, в кредитных картах и персональных компьютерах, поэтому постоянно существует потребность в новых простых числах (чем больше, тем лучше) для генерации секретных кодов. Таким образом, имеется спрос на простые числа, но контроль качества так же важен, как и их производство. Чтобы большому числу присвоить статус простого, его должна проверить специальная организация.

Шифр RSA был опубликован в 1978 г., но повсеместно начал использоваться в качестве метода шифрования лишь в конце 1990 гг. в связи с ростом сети интернет. Поиск больших простых чисел прежде требовал специального программного обеспечения, которое, как правило, можно было купить лишь в специализированных фирмах или в университетах, занимающихся такими исследованиями. Однако экспоненциальный рост вычислительных мощностей и появление более совершенных алгоритмов изменили рынок простых чисел и сделали их гораздо более доступными.

RSA-129

В апреле 1994 г. шифр RSA-129 потерпел полное фиаско. Он был построен на числе, содержащем 129 цифр, о чем объявили авторы этой системы шифрования, предложив желающим взломать его. Около 600 математиков с помощью 1600 добровольцев, найденных через интернет, работали над проблемой, и в конце концов им удалось разложить это число на множители. Однако было подсчитано, что если все компьютеры в мире будут работать параллельно, чтобы взломать код из 1024 цифр, им потребуется время, равное возрасту Вселенной (13,7 миллиарда лет). А теперь представьте себе, что в шифровании с открытым ключом используются числа, содержащие 128,1024 и даже 2048 цифр! Чем больше цифр использует система шифрования, тем устойчивее она к атакам, хотя это, конечно, замедляет процесс расшифровки.

11. Простые числа в природе

Периодические цикады

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

В лесах Теннеси этим летом часть кода, о котором идет речь, в прямом смысле слова выросла прямо из земли. Каждые 13 лет примерно на 6 недель хор насекомых очаровывает всех, кто становится свидетелем этого редкого природного явления. Выживание этих цикад, которых можно найти только в восточных регионах северной Америки, зависит от странных свойств некоторых из самых фундаментальных чисел в математике - простых чисел, чисел, делящихся только на самих себя и других.

Цикады появляются здесь периодически, но их появление всегда происходит в те года, числа которых состоят из простых чисел. В случае с выводком, который появился вокруг Нэшвилле в этом году, то с момента их прошлого появления прошло 13 лет. Выбор 13-детнего цикла не кажется случайным. В разных частях северной Америки есть еще два выводка, жизненный цикл которых также составляет 13 лет. Они возникают в разных регионах и в разные года, но между появлениями этих живых существ проходит ровно 13 лет. Вдобавок, существует еще 12 выводков насекомых, которые появляются через каждые 17 лет.

Вы можете принять эти числа за совершенно случайные. Но это очень любопытно, что не существует цикад с циклом жизни, равным 12, 14, 15, 16 или 18 лет. Однако, посмотрите на этих цикад глазами математика и картина начинает проясняться. Потому, что числа 13 и 17 оба являются неделимыми, это дает цикадам эволюционные преимущества между другими животными, циклы жизни которых являются периодическими, а не простыми числами. Возьмем, к примеру, хищника, который появляется в лесах каждые шесть лет. Тогда восьми- или девятилетние циклы жизни цикад будут совпадать с циклами жизни

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

Согласно одной теории, у цикады имеется паразит, также обладающий длинным жизненным циклом. Цикада, естественно, стремится избавиться от паразита. Если паразит обладает жизненным циклом продолжительностью, скажем 2 года, то цикада стремится избежать жизненного цикла, продолжительность которого в годах делится на 2, так как в противном случае цикада, появляясь из-под земли, и паразит регулярно встречались бы. Аналогично, если бы паразит обладал жизненным циклом продолжительностью 3 года, то цикада стремилась бы избегать жизненных циклов, продолжительность которых в годах выражалась числом, кратным 3. Следовательно, чтобы избежать совпадений с паразитом, лучшей стратегией для цикады было бы иметь жизненный цикл, длящийся простое число лет. Так как ни одно целое число (кроме 1 и 17) не делит число 17, Magicicada septendecim очень редко встречается со своим паразитом. Если продолжительность жизненного цикла паразита составляет 2 года, то цикада встречается с ним только раз в 34 года, а если продолжительность жизненного цикла паразита больше, например, составляет 16 лет, то его встреча с цикадой происходит лишь раз в 272 (= 16·17) года.

«Реванш» для паразита возможен только в двух случаях: при его годичном жизненном цикле и при жизненном цикле продолжительностью 17 лет. Маловероятно, однако, что паразит выживет на протяжении 17 своих поколений подряд, так как первым 16 поколениям будет не на ком паразитировать. С другой стороны, чтобы достичь 17-летней продолжительности жизненного цикла, поколениям паразита необходимо пройти в своей эволюции 16-летний жизненный цикл. Это означало бы, что на каком-то этапе эволюции паразит и цикада не встречались бы на протяжении 272 лет! И в том, и в другом случае большой жизненный цикл продолжительностью в простое число лет способствуют выживанию цикады.

Возможно, именно этим и объясняется, что пресловутый паразит так никогда и не был найден! В гонке на выживание с цикадой паразит, по-видимому, постоянно увеличивал продолжительность своего жизненного цикла до тех пор, пока не наткнулся на 16-летний барьер. После этого паразит на протяжении 272 лет не мог встретиться со своей жертвой и за это время вымер. В результате появилась цикада с жизненным циклом длиной 17 лет. Необходимость в более продолжительном жизненном цикле для цикады отпала, поскольку паразит более не существовал.

Эти насекомые вмешались в математический код, чтобы выжить.

III. Практическая часть. Нахождение простых чисел.

3.1. Алгоритм нахождения простых чисел

1) записать в ряд все натуральные числа от 2 до n

2) 2 (первое число списка) – простое число, обозначим его р

3) необходимо вычеркнуть из ряда все числа, делящиеся на р без остатка (2р, 3р, 4р, и т.д.)

4) следующее незачеркнутое число – 3, и теперь его обозначим как р, снова надо вычеркнуть числа, делящиеся на р без остатка

5) повторять этот алгоритм до тех пор, пока р не станет больше, чем n

6) все невычеркнуые числа в ряду – простые.

3.2. Практическая часть.

1) Запишем натуральные числа от 2 до 30 в ряд:

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

Пройдём по ряду чисел, зачёркивая все числа кратные 2, то есть каждое второе,

начиная с четырёх (2^2=4)

 2)     2 3   5   7   9    11    13     15    17    19    21    23    25    27     29

3) следующее незачеркнутое число 3 – простое.

Пройдём по ряду чисел, зачёркивая все числа кратные 3, то есть каждое третье,

yачиная с девяти (3^2=9)

    2 3   5   7       11    13        17    19       23    25         29

4) следующее незачеркнутое число 5-простое

Пройдём по ряду чисел, зачёркивая все числа, кратные 5, то есть каждое пятое,

начиная с двадцати пяти ( 5^2=25)

2 3   5   7       11    13        17    19       23            29

5) следующее незачеркнутое число 7, его квадрат равен 49 (7^2=49) больше 30, поэтому на этом работа завершена.

Получили ряд простых чисел : 2  3   5   7   11    13   17    19   23   29

  IV.Заключение

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

Изучив весь материал, я пришла к выводу:

•✓ простые числа - загадка с более чем 2000-летней историей, многие ученые на протяжении многих веков вносили свой вклад в изучение этих чисел;

•✓ простые числа представляют собой как бы кирпичики, из которых строятся все остальные числа;

•✓ последовательность простых чисел бесконечна;

•✓ не существует формулы, по которой можно было бы вычислить простые числа;

•✓ не существует самого большого простого числа;

•✓ простые числа - столп всех систем криптографии.

•✓ в настоящее время исследование темы продолжается.

Над проектом я работала с большим интересом и увлечением, меня полностью «захватил» мир таинственных простых чисел, оказывается простые числа, совсем «непростые», и мне остается согласиться с великим Эйлером, который не смог понять эти неуловимые числа:

«Математики уже давно тщетно пытаются найти закономерности в последовательности простых чисел, но у меня есть основания полагать, что это тайна, в которую человеческий разум никогда не сможет проникнуть».

      V. Литература

1.      Школьная энциклопедия «Математика. Том 11». Издательство «Аванта+»., М. 2003

2.      Энциклопедия для детей «История Древнего мира». Издательство «Олимо-пресс Образования»., М 2003

3.      Предметная неделя истории в школе. Составители: И.И. Варакина, С.В. Парецкова. Издательство «Корифей», Волгоград

4.      Шамаев Иван Иванович «Учись открывать новое».  Издательство «Бичик»., Якутск: 1999г

5.      Главный редактор М.Д.Аксёнова, М.: Аванша плюс, 2000г. «Великий мастер индукции Леонард Эйлер»

6.      Сербский И.А. «Что мы знаем и не знаем о простых числах». uka.ru/fag/66114

7.      Издательский дом «Первое сентября». Математика №13, 2002г.

8.      Издательский дом «Первое сентября». Математика №4, 2006г.