Обзор теоретических и вычислительных аспектов проблемы построения больших простых чисел

СОДЕРЖАНИЕ

ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
3
ГЛАВА 1. Основные теоремы, определения и формулы, используемые в дипломной работе .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
5
ГЛАВА 2. История вопроса.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
10
ГЛАВА 3. Генерация больших простых чисел. . . . . . . . . . . . . . . . . . . . . .
20
ЗАКЛЮЧЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
28
ЛИТЕРАТУРА. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
29
















ВВЕДЕНИЕ

     Точно неизвестно, когда в истории математики возникло понятие простого числа. Простое число – положительное целое число, отличное от единицы, которое делится только на единицу и на само себя. Насколько известно, еще Евклид знал, что ряд простых чисел 2, 3, 5, 7, 11, 13,… не обрывается и его можно продолжить бесконечно далеко. Но и до Евклида были известны отдельные свойства простых чисел. Так теорема Ферма о том, что ар – а делится на р, где р – простое число, была известна еще древним китайцам. С более развернутым исследованием простых чисел после Евклида мы встречаемся у Эйлера (1744 г.).  Эйлер доказал, что ряд ?  где суммирование распространяется на все простые числа расходится. В дальнейшем проблемы, касающиеся структуры и места простых чисел в натуральном ряду изучались многими учеными. Здесь следует привести имена Римана, Лежандра, Чебышева, Адамара, Ла Валле Пуссена, Ландау, Харди и Литлвуда, Виноградова и многих других. Хочется отметить, что все проблемы, связанные с изучением простых чисел, очень трудны и десятилетиями остаются открытыми. 
     Во второй половине 20 века интерес к простым числам возрос, в связи с появлением криптографических схем, основанных на открытом ключе. Стойкость самой распространенной криптосистемы RSA основан на экспотенциальной сложности факторизации целых чисел. Поэтому в последние годы возрос интерес к быстрым алгоритмам генерации больших простых чисел. Построение больших простых чисел является еще и критерием мощности вычислительных систем. В настоящее время в сети Интернет существует проект, объединяющий несколько тысяч пользователей, занятых поиском больших чисел Мерсенна. Последний рекорд в этой области - простое число, состоящее из более 6 000 000 цифр.
     Настоящая дипломная работа посвящена обзору теоретических и вычислительных аспектов проблемы построения больших простых чисел.
     Дипломная работа содержит:
     Введение.
     Главу 1. Основные теоремы, определения и формулы, используемые в дипломной работе.
     Главу 2. История вопроса.
     Главу 3. Генерация больших простых чисел.
     Заключение.
     Список литературы.
     Общий объем использованной литературы 6 наименований.
     
     
     
     
     
     
ГЛАВА 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ, ТЕОРЕМЫ И ФОРМУЛЫ, ИСПОЛЬЗУЕМЫЕ В ДИПЛОМНОЙ РАБОТЕ.
     
     1.1 Простое число
     
     Простые числа – целые положительные числа, больше единицы, и не имеющие других делителей, кроме самих себя и единицы: 2, 3, 5, 7, …  Единица же не считается ни простым, ни составным числом, так как единица играет точно такую же роль при умножении, как нуль – при сложении: сколько ни умножай на единицу, ничего не изменится.
     
     1.2. Основная теорема арифметики
     
     Теорема. Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом (если отвлечься от порядка следования сомножителей).
     Действительно, пусть а – целое, большее 1; обозначая буквою р1 его наименьший простой делитель, имеем а = р1а1. Если а1>1, то, обозначая буквою р2 его наименьший простой делитель, имеем а1=р2а2. Если а2>1, то подобно этому находим а2 = р3а3 и т.д., пока не придем к какому-либо аn, равному 1. Тогда получим аn-1 = рn. Перемножив все найденные равенства и произведя сокращение, получим следующее разложение а на простые сомножители:    а= р1р2р3…рn.
     Допустим, что для того же самого а существует и второе разложение на простые сомножители а=q1q2q3…qs. Тогда найдем
     р1р2р3…рn = q1q2q3…qs.
     Правая часть этого равенства делится на q1. Следовательно, по крайней мере один из сомножителей левой части должен делиться на q1. Пусть, например, р1 делится на q1 (порядок следования сомножителей в нашем распоряжении); тогда найдем р1 = q1 (р1 кроме 1 делится только на р1). Сократив обе части равенства на р1 = q1, получим р2р3…рn = q2q3…qs. Повторив прежние рассуждения применительно к этому равенству, получим р3…рn = q3…qs и т.д., пока, наконец, в одной части равенства, например, в левой не сократятся все сомножители. Но одновременно должны сократиться и все сомножители правой части, так как равенство 1 = qn+1…qs при qn+1, …, qs, превосходящих 1, невозможно. Таким образом, второе разложение на простые сомножители тождественно первому и, следовательно, теорема доказана.
     
     1.3. Теорема Евклида
     
     Теорема (Евклида). Множество простых чисел бесконечно.
     Для доказательства этой теоремы необходимо применить теорему о делимости чисел: Если в равенстве вида k+l+ …+n=p+q+…+s относительно всех членов, кроме какого-либо одного, известно, что они делятся на т,  то и этот  член делится на т. 
      И, как следствие из нее, если а  делится на с и  b делится на с, то а±b делится на с. 
     Доказательство. Предположим противное, т.е., что множество простых чисел конечно и равно n. Обозначим эти числа через р1, р2, … , рn; других простых чисел нет. Пусть Р = р1 р2 …рn. Возьмем Q = Р +1. Числа  Р и Q не могут иметь общих делителей,  ибо их общий делитель должен разделить Q - Р =1, что невозможно. Но Q – целое число, большее 1, поэтому оно либо само простое, либо должно делиться на некоторое простое число, отличное от р1, р2, … , рn.
     Следовательно, существует по крайней мере одно простое число, отличное от р1, р2, … , рn, а это противоречит нашему предположению.
     
     1.4. Функция ?(х)
     
     Функция ?(х) с ростом аргумента х практически не отличается от функции .   В 1852 г. П.Л.Чебышев доказал, что предел отношения ?(х) к  при  не может отличаться от единицы. В 1896 г. французский математик Жак Адамар и независимо от него бельгийский математик Ш.Ла Валле Пуссен доказали, что такой предел действительно существует.  Это был так называемый асимптотический закон распределения простых чисел заключающийся в том, что предел отношения ?(х) к  равен 1.
     
     1.5. Понятие сравнения
     
     Тот факт, что числа а и b имеют одинаковые остатки при делении на натуральное число т, немецкий математик Карл Фридрих Гаусс предложил записывать так: а ? b(mоd т). Эта запись называется сравнением.
     Для того чтобы убедиться в сравнимости двух чисел а и b по модулю т, совсем не обязательно находить остатки от деления на т каждого из них. Достаточно рассмотреть их разность: а ? b(mоd т)  в том и только в том случае, когда а – b делится на т.
     
     1.6. Числа Люка
     
     Последовательности   и0,  и1, и2, … ,  и  ?0, ?1, ?2, … , где и0 = 0, и1 = 1, ?0 = 2, ?1 = 4,   а  последующие члены получаются по рекуррентной формуле х j+1 = 4 х j - х j-1, называются последовательностями чисел Люк?.
     
     
     
     
     1.7. Числа Мерсенна
     
     Если число 2n -1 простое, при п = 1, 2, 3, …, его называют числом Мерсенна. ?см. 6?
     
     1.8. Числа Ферма 
     
     Если число Fk  = 2+ 1 простое, при k = 1, 2, 3, …, его называют числом Ферма. ?см. 6?
     
     1.9. Малая теорема Ферма 
     
     Теорема (Ферма). Для любого простого р и любого а ? 1,  не  делящегося  на  р,  справедливо сравнение  ар-1 ? 1 (mоd р).   ?см. 2?
     
      
     
     
     
     
     
     
     ГЛАВА 2. ИСТОРИЯ ВОПРОСА.

     Составить таблицу простых чисел мы можем с помощью старинного способа, придуманного еще в III веке до н.э. Эратосфеном Киренским, хранителем знаменитой Александрийской библиотеки.
     Выпишем несколько подряд идущих чисел, начиная с 2. Двойку оставим, а остальные числа, кратные 2, зачеркнем. Ближайшим незачеркнутым числом будет 3. Оставляем и его, а все остальные числа, кратные 3, зачеркнем. При этом окажется, что некоторые числа уже были вычеркнуты раньше, как например, 6, 12 и др. Следующее наименьшее незачеркнутое  число – это 5. Оставляем пятерку, а остальные числа, кратные 5, зачеркиваем. Повторяя эту процедуру снова и снова, мы в конце концов добьемся того, что незачеркнутыми останутся одни лишь простые числа – они словно просеялись сквозь решето. Поэтому такой способ  и получил название «решето Эратосфена»
     
     Можем ли мы утверждать, что простых чисел столько, «сколько звезд на небе, сколько рыб в воде»? Ответ находим в девятой книге знаменитого сочинения Евклида «Начала» - нетленного памятника Древнего мира. Двадцатая теорема в этой книге утверждает: «Первых (простых) чисел существует больше любого указанного числа их».
     Не о всяком числе можно сразу сказать, простое оно или составное. Возьмем, например, 2003. Если нет под рукой специальных справочных таблиц или компьютера, то воспользуемся решетом Эратосфена. Конечно, число 2003 еще не столь велико, чтобы с трудом просеяться сквозь это решето, но на его примере можно рассмотреть действие другого инструмента.
     Простейшие признаки делимости позволяют сравнительно быстро отказаться от таких делителей, как 2, 3, 5, 7, 11, 13. Проверяем следующее число, 17, - не подходит. Проверяем 19 – тоже не годится. А 23?… с каждой новой попыткой надежда на быстрый успех исчезает. Сколько же чисел-кандидатов нам нужно перебрать, чтобы дойти до 2003?! 
     Однако, если число п равно произведению двух натуральных чисел, то по крайней мере одно из них не больше, чем . Стало быть, на числа-кандидаты, б?льшие  , можно просто не обращать внимания. Поскольку 44 < < 45, то проверить осталось совсем немного чисел – всего лишь 23, 29, 31, 37, 41, 43. Как показывает проверка, ни одно из них не подходит. Следовательно, число 2003 – простое.
     Этот прием, отмеченный еще Леонардо Пизанским, хотя и ускоряет поиск возможных делителей данного числа п, все же оставляет много рутинной работы, если число довольно большое.
     Если взять наугад какое-нибудь достаточно большое натуральное число, то с большой вероятностью оно окажется составным. Ведь по мере удаления в бесконечность решето Эратосфена становится чаще, а значит, простые числа встречаются все реже и реже.
     Первую известную нам таблицу  простых чисел составил итальянский математик Пьетро Антонио Катальди в 1603 г. Она охватывала все простые числа от 2 до 743.
     В 1770 г. немецкий математик Иоганн Генрих Ламберт опубликовал таблицу наименьших делителей всех чисел, не превосходящих 102 000 и не делящихся на 2, 3, 5. Вложив в этот труд поистине колоссальные усилия, Ламберт гарантировал бессмертие тому, кто доведет таблицу делителей до миллиона. На его призыв откликнулись многие вычислители.
     К середине ХIХ в. уже были составлены таблицы наименьших делителей не только первого миллиона, но и следующих, вплоть до девятого. В то же время в Венскую академию поступило семь больших томов рукописных таблиц «Великий канон делителей всех чисел, которые не делятся на 2, 3 и 5, и простых чисел между ними до 100 330 201». Автором этого труда был Якуб Филипп Кулик, профессор высшей математики Пражского университета.
     В дальнейшем поиски простых чисел уже не носили характера массовой охоты, с которой можно сравнить составление таблиц, а превратились в целенаправленный отбор отдельных представителей.
     Итак, по какому же принципу расположены простые числа в натуральном ряде чисел?
     Некоторые представления о распределении простых чисел имели уже древние греки. Из доказательства Евклида следует, например, что они не собраны вместе, а разбросаны по всей числовой оси. Но как часто?
     В 1845 г. французский математик Жозеф Бертран, исследуя таблицу простых чисел в промежутке от 1 до 6 000 000, обнаружил, что между числами п и 2п – 2, где п > 3, содержится по крайней мере одно простое число. Впоследствии это свойство получило название постулата Бертрана, хотя самому Бертрану обосновать его так и не удалось. Доказал его в 1852 г. русский математик Пафнутий Львович Чебышев. Из результатов Чебышева следовала и более точная оценка. Таким образом, даже среди очень больших чисел простые числа не так уж редки. 
     С другой стороны, существуют промежутки, включающие тысячи, миллионы, миллиарды и вообще какое угодно большое количество подряд стоящих натуральных чисел, среди которых нельзя найти ни одного простого! В самом деле, задавшись произвольным большим натуральным числом k, построим ряд чисел  k!+2, k!+3, …, k!+k (здесь k! = 1·2·3·…· k). Каждое из этих чисел составное. Например, число k! + т делится на т, поскольку k! делится на т и само т делится на т.
      Выяснение распределения простых чисел в натуральном ряде чисел является весьма трудной задачей. Она ставиться как изучение асимптотического поведения функции ?(х), обозначающей число простых чисел, не превосходящих положительного числа х. Если рассматривать функцию  ?(х)    (рис.1),    то    при  небольших   значениях х  бросается в глаза ее   нерегулярность.  Однако  стоит  только   уменьшить   масштаб графика в несколько тысяч раз, и нашему взору предстанет красивая плавная линия.  ?см. 5?
       Рис. 1 Графики функции ?(х) в разных масштабах.      
     Пятнадцатилетний Карл Гаусс заинтересовался таблицами простых чисел, помещенными в подаренной ему «Таблице логарифмов». Пытливому уму открылся замечательный математический закон, который сейчас носит название закона распределения простых чисел. Со свойственной гениям прозорливостью Гаусс увидел этот закон, но найти веские аргументы для его обоснования ему было не суждено. Первые результаты в этом направлении принадлежат русскому математику П.Л.Чебышеву. К окончательному выводу в 1896 г. пришли французский математик Жак Адамар и независимо от него бельгийский математик Ш.Ла Валле Пуссен.  В своем доказательстве ученые опирались на результаты немецкого математика Б.Римана, полученные им в, казалось бы, очень далекой от теории чисел области математики  - в теории функции комплексного переменного. 
     В дальнейшем значительные усилия математиков направлялись на уточнение асимптотического закона распределения простых чисел. Вопросы распределения простых чисел изучаются и элементарными методами, и методами математического анализа. Особенно плодотворным является метод, основанный на использовании тождества
      = 
(произведение распространяется на все простые числа р = 2, 3, …), впервые указанного петербургским академиком Л.Эйлером; это тождество справедливо при всех комплексных s с вещественной частью, большей единицы. На основании этого тождества вопросы распределения простых чисел приводятся к изучению специальной функции дзета-функции ?(s), определяемой при Re s > 1 рядом 
     ?(s) = .
     Эта функция использовалась в вопросах распределения простых чисел при вещественных s Чебышевым; Б.Риман указал на важность изучения ?(s) при комплексных значениях s. Риман высказал гипотезу о том, что все корни уравнения ?(s)=0, лежащие в правой полуплоскости, имеют вещественную часть, равную ?. Эта гипотеза до настоящего времени не доказана; ее доказательство дало бы весьма много в решении вопроса о распределении простых чисел. Вопросы распределения простых чисел тесно связаны с проблемой Гольдбаха, с проблемой «близнецов» и другими проблемами аналитической теории чисел. Проблема «близнецов» состоит в том, чтобы узнать, конечно или бесконечно число простых чисел, разнящихся на 2 (таких, например, как 11 и 13). По мере удаления от нуля «близнецов» становится все меньше и меньше, хотя исследования продолжают выявлять эти замечательные и загадочные пары. На 1996 г. рекордсменами считались «близнецы» 242 206 083·238 880±1, найденные с помощью ЭВМ. 
     Среди отдельных классов простых чисел в свое время значительный интерес вызывал вопрос о простых числах вида 2n - 1. Интерес к этому вопросу возник в связи с изучением так называемых совершенных чисел. 
     Легко убедиться, что если число п нечетное составное, то 2n - 1 будет также составным числом, так как из п= аb, 3?а< n, 3?b< n  следует
     2аb - 1 = (2а - 1)(2а(b-1) + 2 а(b-2) + ... +2а + 1).
     Вплоть до 1536 г. было распространено мнение, что верно и обратное, т.е.  простота п влечет за собой простоту 2n – 1, пока Ундалрикус Региус не отметил, что 211 – 1 = 2047 = 23 · 89. Однако длительный период драматических заблуждений был еще впереди. На пороге ХVII столетия Пьетро Антонио Катальди проверил, что 217 – 1 и 219 – 1 суть простые числа, и позволил себе утверждать, что 2n – 1 просто также при  п = 23, 29, 31, 37. В 1640 г. Пьер Ферма установил, что для 23 и 37 это утверждение не верно, а в 1738 г. Л.Эйлер показал его ошибочность для 29.
     Тем временем в 1644 г. французский монах-ученый Марен Мерсенн заявил, что числа 2n -1 просты при п = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 и не просты при остальных 44 простых п меньших 257.  Но и с этим предложением не обошлось без казусов. 
     При больших значениях п определение того, будет ли 2п- 1 простым или составным, требует больших вычислений. Было выяснено, что 231 - 1 (Эйлер, 1750 г.), 261- 1 (Первухин, 1883 г.), 289 - 1 и 2107- 1 (Поуэрс, 1907 и 1914 гг.) - простые числа. До 1952 г. самым большим известным простым числом Мерсенна являлось число 2127- 1; простоту этого числа, имеющего 39 цифр, установил Люка в 1876 г.
     Применение ЭВМ позволило за последние годы найти значительно большие простые числа Мерсенна. (табл.1) ?см. 5?
     Таблица 1. 
Номер числа
п
Год
Номер числа
п
Год
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
5
7
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
-
-
-
-
1456
1588
1588
1772
1883
1911
1914
1876
1952
1952
1952
1952
1952
1957
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
?
4253
4423
9689
9941
11213
19937
21701
23209
44497
86243
110503
132049
216091
756839
859433
1257787
1398269
2976221
1961
1961
1963
1963
1963
1971
1978
1979
1979
1982
1988
1983
1985
1992
1994
1996
1996
1997
     Существует ли бесконечно много простых чисел Мерсенна? Этот вопрос не решен до сих пор и, по-видимому, является чрезвычайно трудным. 
     В одном из своих писем к Марену Мерсенну Пьер Ферма высказал предположение, что все числа вида Fk  = 22 + 1 простые; это как будто подтверждалось тем, что при k = 0, 1, 2, 3, 4 действительно получались простые числа 3, 5, 17, 257, 65537. Следующее число такого вида 2 +1 было уже настолько велико, что Ферма не сумел определить, простое оно или составное.
     В 1739 г. Эйлер показал, что это число составное, и тем самым опроверг гипотезу Ферма. Эйлер указал общий путь для факторизации чисел такого вида, доказав, что все делители числа вида 22 +1  должны иметь вид т2n + 1.
     Простые числа вида 22+1, как известно, связаны с задачей построения правильных многоугольников с помощью циркуля и линейки. Гаусс доказал, что правильный многоугольник может быть построен с помощью циркуля и линейки тогда и только тогда, когда число его сторон п равно 2?р1·р2 ... рs, где все простые числа рj имеют вид 22+1. Среди первых 1000 значений п(п>1) имеется всего только 54 числа такого вида.






ГЛАВА 3. ГЕНЕРАЦИЯ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ.

3.1. Тест на основе малой теоремы Ферма

     Один из способов проверки простоты чисел n порядка 1030 – 1040 основан на малой теореме Ферма.
     Теорема 4.1. Если число а не делится на простое число р, то существует такой показатель ?, что а? – 1 не делится на р, причем ? является делителем р – 1. В частности, ар-1 – 1 всегда делится на р.
     Таким образом, если n простое, то для любого аZ выполнено сравнение 
     аn ? а (mоd n);
     если же при этом (а, n) = 1, то 
     аn-1 ? 1 (mоd n).
     Поэтому для проверки простоты n мы выбираем какое-либо аZ и проверяем выполнение малой теоремы Ферма. Если малая теорема Ферма не выполнена, то n – составное. Если же она выполнена, то мы еще не можем сделать вывод о простоте n, поскольку теорема дает лишь необходимое условие. Этот тест является эффективным для обнаружения составных чисел. Например для 100-значных чисел  n вида 
     n = 1099 + ?,   ? = 1, 3, 5, 7, …, 
мы проверяли выполнение теста 13n-1 ? 1 (mоd n), и первые десять чисел, прошедших этот тест, оказались впоследствии простыми.
     Однако существуют такие составные числа n, называемые числами Кармайкла, что для любого  аZ выполнено сравнение аn ? а (mоd n). Наименьшее такое n равно 561 = 3 · 11 · 17. Докажем, что 561 – число Кармайкла. Сравнение а561?а(mоd 561) равносильно тому, что а561?а(mоd 3), а561? а (mоd 11), а561? а (mоd 17). Если 3| а, то а561? а? 0 (mоd 3). Если же 3 не делит а, то а2?1(mоd 3), откуда а560? 1 (mоd 3),  а561? а (mоd 3). Аналогичная проверка делается для 11 и 17. Чисел Кармайкла бесконечно много.
     Таким образом, для проверки простоты чисел малой теоремы Ферма недостаточно.
     
    3.2. Тесты на простоту для чисел специального вида
    
     Для проверки простоты чисел Ферма существует следующий тест.
     Теорема 4.2. Число n = Fk при  k >0 является простым тогда и только тогда, когда 
     3? -1(mоd n).
     Однако числа Ферма растут быстро, и поэтому данный тест так же быстро становится неэффективным.
     Для проверки простоты чисел Мерсенна используется следующий тест.
     
     Теорема 4.3. Пусть q – простое число, q>2, n = 2q – 1. Рассмотрим последовательность L0, L1, L2, … , определяемую соотношениями
     L0 = 4;  	Lj+1?L- 2(mоd n).
     Число n - простое тогда и только тогда, когда Lq-2 ?0 (mоd n).
     Теорема 4.4. Пусть р – простое число,  р ? 3 (mоd 4), Мр = 2р – 1 – число Мерсенна. Число Ферма Fр  является простым тогда и только тогда, когда
     М? -1 (mоd Fр).
    
3.4. (N± 1)-методы проверки простоты чисел и построения больших простых чисел

     В этом пункте главы 3 будут рассмотрены методы, с помощью которых можно проверять простоту натурального числа N, если известно полное или частичное разложение N - 1 или N + 1 на множители. 
     Докажем сначала теорему, относящуюся к  (N -1)-методам проверки простоты чисел.
     Теорема 4.5. Пусть п ? N, п > 1, п нечетно,   п - 1 = - известное  разложение  п -1  на простые  множители.  Если для каждого i = 1 , … , k  существует такое аi ? N, что
     а? 1(mоd п),   анесравнимо с 1 (mоd п),
     то п -  простое число.
     Как применять теорему 4.5 на практике? Зная разложение п - 1 множители, надо либо перебором подряд а = 2, 3, ..., либо случайным выбором а искать числа аi, удовлетворяющие условию теоремы. Если для некоторого а, 1< а < п, окажется, что ап-1 несравнимо с 1 (mоd п), то п составное. Если же мы найдем а1, … , аk, то тем самым покажем, что а простое.
     Заметим, что мы фактически уже пользовались методом теоремы 4.5 применительно к числам Ферма. При этом числа аi  искать было не нужно, нам заранее известно, что а = 3.
     Аналогичный результат справедлив в случае, когда известно полное разложение п +1 на множители.
     Вернемся теперь к (N - 1)-методам проверки простоты чисел и покажем, как с их помощью можно строить большие простые числа.
     Теорема 4.6. Пусть  п ? N,   п > 1,   п  нечетно, п - 1 = F1 · R1, где (F1, R1) = 1. Пусть известно полное разложение F1 = на простые сомножители. Если для любого j = 1, …, k  найдется такое аj ? N, что
     а? 1 (mоd п),      (аj- 1, п) = 1,
     то, при условии, что
     F1?,
     число п — простое.
     Покажем, как с помощью теоремы 4.6 можно строить большие простые числа. Мы строим последовательность простых чисел  р1 < р2 < р3 < …, пока не найдем простое число нужной нам величины. Простое нечетное число р1 выбираем   произвольно,  например,   р1 = 3. Пусть мы уже построили простое   рi-1.   Выберем    случайное   r,    1 ?  r ?  рi-1 - 1.   Пусть    r = 2s · t,     t - нечетно.  Тогда  в   качестве кандидата на очередное простое  рi    возьмем  п = 2r рi-1 + 1 = 2 s +1  ? ? рi-1· t  + 1.
     Положим F1 =2s+1рi-1, R1= t.  Очевидно,  что  (F1, R1)=1. Далее, F1 > , поскольку п = 2s+1рi-1 t + 1 < 2s+2р2i-1 ? F21. Следовательно, для доказательства простоты п нужно найти (перебором) числа а1 и а2 такие, что
     а? а? 1(mоd п), (а- 1, п) = (а - 1, п) = 1.
     Если в ходе перебора найдется такое а, что ап-1 несравнимо с 1(mоd п), или один из двух наибольших общих делителей с п дает нетривиальный делитель числа п, то п — составное; тогда нужно выбрать другое случайное r (и другое п). Если же мы докажем простоту п, то положим рi = п. 
     Другой способ применения теоремы 4.6 заключается в следующем, Мы снова строим цепочку простых чисел, и пусть построено рi-1 > 3. Выберем случайное четное  r, 1 ? r ? рi-1- 3, и положим п = рi-1r+ 1. Пусть F1 = рi-1,_R1 = r, (F1, R1)=1. Нам нужно найти всего лишь одно натуральное а такое, что ап-1 ? 1 (mоd п), (аr - 1, п) = 1 (поскольку  = r).  Действительно, неравенство  F1 = рi-1 >    выполнено,  так как 
     п = рi-1r+ 1 ? рi-1(рi-1 – 3) + 1 = р2i-1 – 3рi-1 + 1 ? р2i-1 – 3 · 5 + 1 < р2i-1.
     Перебор а осуществляется так же, как в предыдущем способе.
     Следующая теорема является более эффективной для построения больших простых, поскольку в ней отсутствует вычисление наибольшего общего делителя.
     Теорема 4.7. (Диемитко). Пусть п = 2rq + 1, где q - нечетное простое число, и r ? 2q+ 1. Если существует такое а ? N, что
     ап-1 ? 1 (mоd п),     а2r несравнимо с 1 (mоd п),
     то п — простое число.
     Доказательство. Пусть п — составное, п = рN, где р — простое, N>1. Поскольку п не делит а2r-1, то найдется простой делитель п, который входит в  п  в  большей  степени,  чем  в  а2r-1.   Его  и  обозначим через р.  Тогда ?р(п) > ?р(а2r-1), и при s = ?р (а2r-1)+1 ? 1 имеем рs |п, рs не делит а2r-1.
     Пусть d - порядок а (mоd рs) в Z/рsZ. Число d определено и d|п-1=2rq, поскольку ап-1 ? 1 (mоd п). Кроме того, d|?(рs) = рs-1 (р - 1). Но из соотношения а2r несравнимо с 1 (mоd рs) следует, что d не делит 2r.  Значит, q|d. Поэтому q|рs-1(р-1). Числа q и р различны, так как р|п, q|п- 1. Следовательно, q|р-1. Отсюда р?1(mоd q)  и в силу нечетности р и q получаем, что р?1(mоd 2q). Кроме того, п?1(mоd 2q). Поэтому, так как п = рN, N ?1(mоd 2q). Поскольку р> 1 и N >1, то р ? 1 + 2q, N ?1 +2q. Значит, п=рN ? (1 + 2q)2. Однако п = 2rq + 1 ? 2q(2q + 1) + 1 < (1 + 2q)2. Полученное противоречие доказывает теорему. 
     Эта теорема лежит в основе алгоритма генерации простых чисел в отечественном стандарте на цифровую подпись ГОСТ Р34.10-94. В ней в качестве а выбираются не очень высокие степени числа 2, а r находится перебором. ?см. 4?
     Замечание. Из теоремы 4.7 также следует метод построения простых чисел, аналогичный предыдущим.
     Замечание. Если заменить неравенство r? 2q + 1 на неравенство r? 2q + 2, то утверждение теоремы 4.7 о простоте п будет неверным. Можно даже привести пример а и п, для которых условия теоремы будут выполнены, но п будет составным. Следующая теорема показывает, как можно увеличить верхнюю границу для r.
     Теорема 4.8. Пусть п = 2rq + 1, где q - простое число, r ? 4q + 2. Пусть существует такое а ? N. Что
     ап-1 ? 1 (mоd п),     а2r несравнимо с 1 (mоd п).
     Тогда  либо  п - простое,  либо  п=р2,   где р=2q+1 - простое число и ар-1?1(mоd р2).
     Доказательство. Пусть п - составное, п = рN, где р и N те же, что в доказательстве теоремы 4.7. Мы показали, что
     п ? р ? N ? 1(mоd 2q).
Если одно из чисел р и N строго больше 1 + 2q, то оно больше или равно 1 + +4q , и тогда п = рN ? (1+2q)(1+4q) = 8q2 + 6q+1. Но по условию п?2q(4q+2)+1=8q2+4q+1. Следовательно, р = N = 1 + 2q, п = р2. Осталось показать, что ар-1 ? 1 (mоd р2). Действительно, по условию ар-1?1(mоd р2), и по теореме Эйлера а?1(mоd р2), откуда следует требуемое сравнение. 
     Замечание. Если q известно, то проверить равенство п = (2q + 1)2 очень легко. То есть, узнав а, мы будем знать, простое п или составное. Тест теоремы 4.8 очень эффективен для построения больших простых чисел, так как чем больше верхняя граница для выбора случайного r, тем дальше мы можем «шагнуть» при построении очередного простого числа. ?см. 3?
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     ПРИМЕРЫ
     
     Для нахождения больших простых чисел мы пользовались теоремой Диемитко. Вот, например, некоторые из них: 
     п = 2rq + 1;
     q – простое нечетное;
     r ? 2q + 1;
     а – небольшие степени числа 2.
     ап-1 ? 1 (mоd п);     
     а2r несравнимо с 1 (mоd п).
     
     Пример 1. 
     q = 3;  r ? 1;  п = 7;  а = 4.
     46 ? 1 (mоd 7);
     42 несравнимо с 1 (mоd 7).
     
     Пример 2. 
     q = 5;  r ? 7;  п = 71;  а = 2.
     270 ? 1 (mоd 71);
     214 несравнимо с 1 (mоd 71).
     
     Пример 3. 
     q = 13;  r ? 5;  п = 131;  а = 2.
     2130 ? 1 (mоd 131);
     210 несравнимо с 1 (mоd 131).
     
     Алгоритм решения 
     CLS
     P = 0:  R = 0
     INPUT  «Введите простое нечетное число»; Q
     WHILE (P = 0)
     	WHILE (R > 2 * Q + 1)
     		R = R + 1
     	WEND
     	N = 2 * Q * R + 1
     	A = 2
     	FOR  I = 1  TO  3
     		IF  A ^ (N-1) – 1 MOD N = 0 AND A ^ (2*R) – 1 MOD N <> 0 THEN  I = 3 : P = 1
     		A = A * 2 
     	NEXT
     	R = R + 1
     WEND
     PRINT  N
      
     
     
ЗАКЛЮЧЕНИЕ

     Теорема  Диемитко является достаточным условием для нахождения простых чисел. Ученые находятся в процессе поиска тестов для нахождения больших простых чисел. Эта задача на сегодняшний момент является очень актуальной.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
ЛИТЕРАТУРА

1. Виноградов И.М. Основы теории чисел. М.: «Наука», 1981 г.
2. Бухштаб А.А. Теория чисел.  М.: «Просвещение», 1966 г.
3. Василенко О.Н.  Теоретико – числовые  алгоритмы  в криптографии.  М.: МЦНМО, 2003 г.
4. Черемушкин  А.В. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002 г.
5. Энциклопедия для детей. Т 11, Математика, (Гл.редактор Э68 М.Д.Аксенова), М.: Аванта +, 1998 г.
6. Математическая энциклопедия (Гл.редактор И.М.Виноградов, т.4, 5 «Советская энциклопедия»), 1984 г.


     
     
     
     

.......................