Применение алгоритма RSA для шифрования потоков данных — страница 10

заменить простой модуль составным моду­лем 3. КАЧЕСТВЕННАЯ ТЕОРИЯ АЛГОРИТМА RSA Существует довольно эффективный способ убедиться, что заданное число является составным, не разлагая это число на множители. Согласно малой теореме Ферма, если число простое, то для любого целого (9) Если же при каком-то это сравнение нарушается, можно утверждать, что - составное. Проверка (9) не требует больших вычислений, это следует из алгоритма 1.

Вопрос только в том, как найти для составного целое число К сожалению, такой подход не всегда даёт то, что хотелось бы. Име­ются составные числа с условием различны, причем делится на каждую разность В 1976 г. Миллер предложил заменить проверку (9) проверкой несколь­ко иного условия. Если - простое число, нечётно, то согласно ма­лой теореме Ферма для каждого с условием хотя бы одна из скобок в произведении делится на Пусть - нечётное

составное число, нечётно. Назовем целое число 1) не делится на 2) или существует целое Из сказанного ранее следует, что для простого числа не существует хороших чисел составное число, то, как доказал Рабин, их существует не менее Теперь можно построить вероятностный алгоритм, отличающий со­ставные числа от простых. 3.1. Алгоритм, доказывающий непростоту числа 1) Выберем случайным образом число этого числа указанные выше свойства 1)

и 2) п.2. 2) Если хотя бы одно из них нарушается, то число составное. 3) Если выполнены оба условия 1) и 2) п.2, возвращаемся к шагу 1. Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей повторений не превосходит Миллер предложил детерминированный алгоритм определения состав­ных чисел, имеющий сложность из указанного промежутка нарушается

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

группу по умножению. Единичным элементом этой группы является так называемый главный характер С каждым характером может быть связана так называемая - функция Дирихле - функция комплексного переменного и может быть аналитически продолжена на всю комплексную плос­кость. Следующее соотношение связывает L - функцию, отвечающую главному характеру, с дзета-функцией Римана L -функций Дирихле, расположенные в полосе В 1952 г. Анкени с