Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

[pic]. (10)
Тогда каждый простой делитель [pic] числа [pic] удовлетворяет сравнению

[pic].

Доказательство. Пусть [pic] - простой делитель числа [pic], a [pic] - некоторый делитель [pic]. Из условий (10) следует, что в поле вычетов [pic] справедливы соотношения

[pic].

(11)
Обозначим буквой [pic] порядок элемента [pic] в мультипликативной группе поля [pic]. Первые два из соотношений (11) означают, что [pic] входит в разложение на простые множители числа [pic] в степени такой же, как и в разложение [pic], а последнее - что [pic] делится на [pic]. Таким образом, каждый простой делитель числа [pic] входит в разложение [pic] в степени не меньшей, чем в [pic], так что [pic] делится на [pic]. Кроме того, [pic] четно. Теорема 2 доказана.

Следствие. Если выполнены условия теоремы 2 и [pic], то [pic] - простое число.

Действительно, пусть [pic] равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем [pic]. Но тогда [pic]. Противоречие и доказывает следствие.

Покажем теперь, как с помощью последнего утверждения, имея большое простое число [pic], можно построить существенно большее простое число
[pic]. Выберем для этого случайным образом чётное число [pic] на промежутке
[pic] и положим [pic]. Затем проверим число [pic] на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем [pic] некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что [pic] - составное число, следует выбрать новое значение [pic] и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число [pic], выдержавшее испытания алгоритмом 5 достаточно много раз. В этом случае появляется надежда на то, что [pic] - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2.

Для этого можно случайным образом выбирать число [pic], и проверять для него выполнимость соотношений

[pic].

(12)
Если при выбранном [pic] эти соотношения выполняются, то, согласно следствию из теоремы 2, можно утверждать, что число [pic] простое. Если же эти условия нарушаются, нужно выбрать другое значение [pic] и повторять эти операции до тех пор, пока такое число не будет обнаружено.

Предположим, что построенное число [pic] действительно является простым. Зададимся вопросом, сколь долго придётся перебирать числа [pic], пока не будет найдено такое, для которого будут выполнены условия (12).
Заметим, что для простого числа [pic] первое условие (12), согласно малой теореме Ферма, будет выполняться всегда. Те же числа [pic], для которых нарушается второе условие (12), удовлетворяют сравнению [pic]. Как известно, уравнение [pic] в поле вычетов [pic] имеет не более [pic] решений. Одно из них [pic]. Поэтому на промежутке [pic] имеется не более
[pic] чисел, для которых не выполняются условия (12). Это означает, что, выбирая случайным образом числа [pic] на промежутке [pic], при простом
[pic] можно с вероятностью большей, чем [pic], найти число [pic], для которого будут выполнены условия теоремы 2, и тем доказать, что [pic] действительно является простым числом.

Заметим, что построенное таким способом простое число [pic] будет удовлетворять неравенству [pic], т. е. будет записываться вдвое большим количеством цифр, чем исходное простое число [pic]. Заменив теперь число
[pic] на найденное простое число [pic] и повторив с этим новым [pic] все указанные выше действия, можно построить еще большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами
(простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз. можно построить простые числа нужной величины.

Обсудим теперь некоторые теоретические вопросы, возникающие в связи с нахождением числа [pic], удовлетворяющего неравенствам [pic], и такого, что
[pic] - простое число. Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия [pic], [pic] содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии. Опенка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю. В. Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии [pic] не превосходит [pic], где [pic] - некоторая достаточно большая абсолютная постоянная.

Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа [pic] не существует. Тем не менее опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии встречаются достаточно близко к её началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел [pic] с условием, что число [pic] также простое, т. е. простым является уже первый член прогрессии.

Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором [pic] число [pic] составное, можно следующее значение [pic] взять равным [pic] и действовать так далее, пока не будет найдено простое число [pic]. И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число [pic]. Перебор чисел [pic] до того момента, как мы наткнемся на простое число [pic] окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами [pic] и [pic] в натуральном ряде доказано лишь, что [pic], что, конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера
(1936 г.), что [pic], дающая вполне приемлемую опенку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно.

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

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

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

3.3. Проверка большого числа на простоту

Есть некоторое отличие в постановках задач предыдущего и настоящего пунктов. Когда мы строим простое число [pic], мы обладаем некоторой дополнительной информацией о нем, возникающей в процессе построения.
Например, такой информацией является знание простых делителей числа [pic].
Эта информация иногда облегчает доказательство простоты [pic].

В этом пункте мы предполагаем лишь, что нам задано некоторое число
[pic], например, выбранное случайным образом на каком-то промежутке, и требуется установить его простоту, или доказать, что оно является составным. Эту задачу за полиномиальное количество операций решает указанный в п. 3 алгоритм Миллера. Однако, справедливость полученного с его помощью утверждения зависит от недоказанной расширенной гипотезы Римана.
Если число [pic] выдержало испытания алгоритмом 5 для 100 различных значений параметра [pic], то, по-видимому, можно утверждать, что оно является простым с вероятностью большей, чем [pic]. Эта вероятность очень близка к единице, однако всё же оставляет некоторую тень сомнения на простоте числа [pic]. В дальнейшем в этом пункте мы будем считать, что заданное число [pic] является простым, а нам требуется лишь доказать это.

В настоящее время известны детерминированные алгоритмы различной сложности для доказательства простоты чисел. Мы остановимся подробнее на одном из них, предложенном в 1983 г. в совместной работе Адлемана.
Померанца и Рамели. Для доказательства простоты или непростоты числа [pic] этот алгоритм требует [pic] арифметических операций. Здесь [pic] - некоторая положительная абсолютная постоянная. Функция [pic] хоть и медленно, но всё же возрастает с ростом [pic], поэтому алгоритм не является полиномиальным. Но всё же его практические реализации позволяют достаточно быстро тестировать числа на простоту. Существенные усовершенствования и упрощения в первоначальный вариант алгоритма были внесены в работах X.
Ленстры и А. Коена. Мы будем называть описываемый ниже алгоритм алгоритмом
Адлемана - Ленстры.

В основе алгоритма лежит использование сравнений типа малой теоремы
Ферма, но в кольцах целых чисел круговых полей, т. е. полей. порождённых над полем [pic] числами [pic] - корнями из 1. Пусть [pic] - простое нечётное число и [pic] — первообразный корень по модулю [pic], т. е. образующий элемент мультипликативной группы поля [pic], которая пиклична.
Для каждого целого числа [pic], не делящегося на [pic], можно определить его индекс, [pic], называемый также дискретным логарифмом, с помощью сравнения [pic]. Рассмотрим далее два простых числа [pic], [pic] с условием, что [pic] делится на [pic], но не делится на [pic].

Следующая функция, определённая на множестве целых чисел.

Рекомендуем скачать другие рефераты по теме: оценка реферата, диплом на тему.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата