Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[4]

делится на N. Обращение этого свойства можно использовать, чтобы отличать составные числа от простых.

Пусть N - нечётное составное число. N - 1 = 2s t, где t нечётно. Назовем целое число а. 1 < а < N. «хорошим» для N. если нарушается одно из двух условий: а) N не делится на а:

/3) а* = 1 (mod N) или существует целое к, 0 к < s, такое, что

а24 = -1 (mod N).

Из сказанного ранее следует, что для простого числа N не существует хороших чисел а. Если же N составное число, то. как доказал Рабин. их существует не менее (А - 1).

Теперь можно построить вероятностный алгоритм, отличающий составные числа от простых.

5. Алгоритм, доказывающий непростоту числа.

1)Выберем случайным образом число а. 1 < а < N. и проверим для этого числа указанные выше свойства а) и (3).

2)Если хотя бы одно из них нарушается, то число N составное.

3)Если выполнены оба условия а) и (3). возвращаемся к шагу 1.

Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей 4-1. А вероятность не определить его после к повторений не превосходит 4~к. т. е. убывает очень быстро.

Миллер предложил детерминированный алгоритм определения составных чисел, имеющий сложность 0(ln3 N), однако справедливость его результата зависит от недоказанной в настоящее время так называемой расширенной гипотезы Римана. Согласно этому алгоритму достаточно проверить условия а) и /3) для всех целых чисел а, 2 а 70 In2 А. Если при каком-нибудь а из указанного промежутка нарушается одно из условий а) или 13), число N составное. В противном случае оно будет простым или степенью простого числа. Последняя возможность, конечно, легко проверяется.

Напомним некоторые понятия, см. [5]. необходимые для формулировки расширенной гипотезы Римана. Они понадобятся нам и в дальнейшем. Пусть то 2 - целое число. Функция \ -> С называется характером Дирихле по модулю то. или просто характером, если эта функция периодична с периодом то. отлична от нуля только на числах, взаимно простых с то. и мультипликативна, т. е. для любых целых и, v выполняется равенство x{uv) = x{u)x{v)- Для каждого то существует ровно (f(m)


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

С каждым характером может быть связана так называемая L-функ-ния Дирихле - функция комплексного переменного s, определённая ря-

> 1 и может быть аналитически продолжена на всю комплексную плоскость. Следующее соотношение L(s,xo) = C(s) Jf(l ~ P~s) связывает L-

функцию, отвечающую главному характеру, с дзета-функцией Римана

ные нули всех L-функний Дирихле, расположенные в полосе 0 < Res < 1, лежат на прямой Res = \. В настоящее время не доказана даже простейшая форма этой гипотезы - классическая гипотеза Римана. утверждающая такой же факт о нулях дзета-функции.

В 1952 г. Анкени с помощью расширенной гипотезы Римана доказал, что для каждого простого числа q существует квадратичный невычет а. удовлетворяющий неравенствам 2 а 70 In2 q. Константа 70 была сосчитана позднее. Именно это утверждение и лежит в основе алгоритма Миллера. В 1957 г. Берджесс доказал существование такого невычета без использования расширенной гипотезы Римана. но с худшей оценкой

2 а q4Se -\-е. справедливой при любом положительном е и q. большем некоторой границы, зависящей от е.

Алгоритм Миллера принципиально отличается от алгоритма 5. так как полученное с его помощью утверждение о том. что число N - составное, опирается на недоказанную расширенную гипотезу Римана и потому может быть неверным. В то время как вероятностный алгоритм 5 даёт совершенно правильный ответ для составных чисел. Несмотря на отсутствие опенок сложности, на практике он работает вполне удовлетворительно.

4. Как строить большие простые числа

Мы не будем описывать здесь историю этой задачи, рекомендуем обратиться к книге [7] и обзорам [10. 11]. Конечно же. большие простые числа можно строить сравнительно быстро. При этом можно обеспечить

аналитична в области Res >

C(s) V . 1> п=0

асширенная гипотеза Римана утверждает, что комплекс-


их случайное распределение в заданном диапазоне величин. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.

Теорема 2. Пусть N. 5 - нечётные натуральные числа. N - 1 = = S R. причем для каждого простого делителя q числа 5 существует целое число а такое, что

лг 1N-1

а = 1 (mod N), {а я -1.ЛГ) = 1.(10)

Тогда каждый простой делитель р числа N удовлетворяет сравнению

р = 1 (mod 25).

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

aN~1 = 1. а V ф 1. а131 = 1.(11)

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

Следствие. Если выполнены условия теоремы 2 и R 45 + 2, то N - простое число.

Действительно, пусть N равняется произведению не менее двух простых чисел. Каждое из них. согласно утверждению теоремы 2. не меньше, чем 25 + 1. Но тогда (25 + 1)2 N = SR + 1 452 + 25 + 1. Противоречие и доказывает следствие.

Покажем теперь, как с помошью последнего утверждения, имея большое простое число 5. можно построить сушественно большее простое число N. Выберем для этого случайным образом чётное число R на промежутке 5i? 45+ 2и положим N = SR + 1. Затем проверим число N на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем N некоторое количество раз с помошью алгоритма 5. Если при этом выяснится, что N - составное число, следует выбрать новое значение R и опять повторить вычисления. Так следует делать до



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9]