Применение алгоритма RSA для шифрования потоков данных
.
Заменив теперь
число
на найденное
простое число
и повторив с
этим новым
все указанные
выше действия,
можно построить
еще большее
простое число.
Начав с какого-нибудь
простого числа,
скажем, записанного
10 десятичными
цифрами (простоту
его можно проверить,
например, делением
на маленькие
табличные
простые числа),
и повторив
указанную
процедуру
достаточное
число раз. можно
построить
простые числа
нужной величины.
Обсудим
теперь некоторые
теоретические
вопросы, возникающие
в связи с нахождением
числа
,
удовлетворяющего
неравенствам
,
и такого, что
- простое число.
Прежде всего,
согласно теореме
Дирихле, доказанной
еще в 1839 г., прогрессия
,
содержит бесконечное
количество
простых чисел.
Нас интересуют
простые числа,
лежащие недалеко
от начала прогрессии.
Опенка наименьшего
простого числа
в арифметической
прогрессии
была получена
в 1944 г. Ю. В. Линником.
Соответствующая
теорема утверждает,
что наименьшее
простое число
в арифметической
прогрессии
не превосходит
,
где
- некоторая
достаточно
большая абсолютная
постоянная.
Таким
образом, в настоящее
время никаких
теоретических
гарантий для
существования
простого числа
не существует.
Тем не менее
опыт вычислений
на ЭВМ показывает,
что простые
числа в арифметической
прогрессии
встречаются
достаточно
близко к её
началу. Упомянем
в этой связи
гипотезу о
существовании
бесконечного
количества
простых чисел
с условием, что
число
также простое,
т. е. простым
является уже
первый член
прогрессии.
Очень важен
в связи с описываемым
методом построения
простых чисел
также вопрос
о расстоянии
между соседними
простыми числами
в арифметической
прогрессии.
Ведь убедившись,
что при некотором
число
составное,
можно следующее
значение
взять равным
и действовать
так далее, пока
не будет найдено
простое число
.
И если расстояние
между соседними
простыми числами
в прогрессии
велико, нет
надежды быстро
построить
нужное число
.
Перебор чисел
до того момента,
как мы наткнемся
на простое
число
окажется слишком
долгим. В более
простом вопросе
о расстоянии
между соседними
простыми числами
и
в натуральном
ряде доказано
лишь, что
,
что, конечно,
не очень хорошо
для наших целей.
Вместе с тем
существует
так называемая
гипотеза Крамера
(1936 г.), что
,
дающая вполне
приемлемую
опенку. Примерно
такой же результат
следует и из
расширенной
гипотезы Римана.
Вычисления
на ЭВМ показывают,
что простые
числа в арифметических
прогрессиях
расположены
достаточно
плотно.
В качестве
итога обсуждения
в этом пункте
подчеркнём
следующее: если
принять на
веру, что наименьшее
простое число,
а также расстояние
между соседними
простыми числами
в прогрессии
при
оцениваются
величиной
,
то описанная
схема построения
больших простых
чисел имеет
полиномиальную
опенку сложности.
Кроме того,
несмотря на
отсутствие
теоретических
опенок времени
работы алгоритмов,
отыскивающих
простые числа
в арифметических
прогрессиях
со сравнительно
большой разностью,
на практике
эти алгоритмы
работают вполне
удовлетворительно.
На обычном
персональном
компьютере
без особых
затрат времени
строятся таким
способом простые
числа порядка
.
Конечно, способ конструирования простых чисел для использования в схеме RSA должен быть массовым, а сами простые числа должны быть в каком-то смысле хорошо распределёнными. Это вносит ряд дополнительных осложнений в работу алгоритмов.
Наконец,
отметим, что
существуют
методы построения
больших простых
чисел, использующие
не только простые
делители
,
но и делители
чисел
.
В основе их
лежит использование
последовательностей
целых чисел,
удовлетворяющих
линейным рекуррентным
уравнениям
различных
порядков. Отметим,
что последовательность
,
члены которой
присутствуют
в формулировке
малой теоремы
Ферма, составляет
решение рекуррентного
уравнения
первого порядка
.
3.3. Проверка большого числа на простоту
Есть некоторое
отличие в постановках
задач предыдущего
и настоящего
пунктов. Когда
мы строим простое
число
,
мы обладаем
некоторой
дополнительной
информацией
о нем, возникающей
в процессе
построения.
Например, такой
информацией
является знание
простых делителей
числа
.
Эта информация
иногда облегчает
доказательство
простоты
.
В этом пункте
мы предполагаем
лишь, что нам
задано некоторое
число
,
например, выбранное
случайным
образом на
каком-то промежутке,
и требуется
установить
его простоту,
или доказать,
что оно является
составным. Эту
задачу за
полиномиальное
количество
операций решает
указанный в
п. 3 алгоритм
Миллера. Однако,
справедливость
полученного
с его помощью
утверждения
зависит от
недоказанной
расширенной
гипотезы Римана.
Если число
выдержало
испытания
алгоритмом
5 для 100 различных
значений параметра
,
то, по-видимому,
можно утверждать,
что оно является
простым с
вероятностью
большей, чем
.
Эта вероятность
очень близка
к единице, однако
всё же оставляет
некоторую тень
сомнения на
простоте числа
.
В дальнейшем
в этом пункте
мы будем считать,
что заданное
число
является простым,
а нам требуется
лишь доказать
это.
В настоящее
время известны
детерминированные
алгоритмы
различной
сложности для
доказательства
простоты чисел.
Мы остановимся
подробнее
на одном из
них, предложенном
в 1983 г. в совместной
работе Адлемана.
Померанца и
Рамели. Для
доказательства
простоты или
непростоты
числа
этот алгоритм
требует
арифметических
операций. Здесь
- некоторая
положительная
абсолютная
постоянная.
Функция
хоть и медленно,
но всё же возрастает
с ростом
,
поэтому алгоритм
не является
полиномиальным.
Но всё же его
практические
реализации
позволяют
достаточно
быстро тестировать
числа на простоту.
Существенные
усовершенствования
и упрощения
в первоначальный
вариант алгоритма
были внесены
в работах X.
Ленстры и А.
Коена. Мы будем
называть описываемый
ниже алгоритм
алгоритмом
Адлемана - Ленстры.
В основе
алгоритма лежит
использование
сравнений типа
малой теоремы
Ферма, но в кольцах
целых чисел
круговых полей,
т. е. полей. порождённых
над полем
числами
- корнями из 1.
Пусть
- простое нечётное
число и
— первообразный
корень по модулю
,
т. е. образующий
элемент мультипликативной
группы поля
,
которая пиклична.
Для каждого
целого числа
,
не делящегося
на
,
можно определить
его индекс,
,
называемый
также дискретным
логарифмом,
с помощью сравнения
.
Рассмотрим
далее два простых
числа
,
с условием, что
делится на
,
но не делится
на
.
Следующая функция, определённая на множестве целых чисел.

является
характером
по модулю
и порядок этого
характера равен
.
Сумма

называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.
Теорема
3. Пусть
- нечетное простое
число,
.
Тогда в кольце
выполняется
сравнение
.
Если при
каких-либо
числах
сравнение из
теоремы 3 нарушается.
можно утверждать,
что
составное
число. В противном
случае, если
сравнение
выполняется,
оно даёт некоторую
информацию
о возможных
простых делителях
числа
.
Собрав такую
информацию
для различных
,
в конце концов
удаётся установить,
что
имеет лишь один
простой делитель
и является
простым.
В случае
легко проверить,
что сравнение
из теоремы 3
равносильно
хорошо известному
в элементарной
теории чисел
сравнению
, (13)
где
- так называемый
символ Якоби.
Хорошо известно
также, что последнее
сравнение
выполняется
не только для
простых
,
но и для любых
целых
,
взаимно простых
с
.
Заметим также,
что для вычисления
символа Якоби
существует
быстрый алгоритм,
основанный
на законе взаимности
Гаусса и. в некотором
смысле, подобный
алгоритму
Евклида вычисления
наибольшего
общего делителя.
Следующий
пример показывает.
каким образом
выполнимость
нескольких
сравнений типа
(13) даёт некоторую
информацию
о возможных
простых делителях
числа
.
Пример
(X.
Ленстра). Пусть
— натуральное
число,
.
для которого
выполнены
сравнения
,
(14)
а кроме
того с некоторым
целым числом
имеем
.
(15)
Как уже
указывалось,
при простом
сравнения (14)
выполняются
для любого
,
взаимно простого
с
,
а сравнение
(15) означает, что
есть первообразный
корень по модулю
.
Количество
первообразных
корней равно
,
т. е. достаточно
велико. Таким
образом, число
с условием
(15) при простом
может быть
найдено достаточно
быстро с помощью
случайного
выбора и последующей
проверки (15).
Докажем,
что из выполнимости
(14-15) следует, что
каждый делитель
числа
удовлетворяет
одному из сравнений
или
.
(16)
Не уменьшая
общности, можно
считать, что
- простое число.
Введем теперь
обозначения
,
где
и
- нечётные числа.
Из (15) и сравнения
следует, что
.
Далее, согласно
(14). выполняются
следующие
сравнения
,
означающие (в силу того, что символ Якоби может равняться лишь -1 или +1), что
.
При
это равенство
означает, что
при
,
и, следовательно,
.
Если же
,
то имеем
и
.
Этим (16) доказано.
Информация
такого рода
получается
и в случае
произвольных
простых чисел
и
с указанными
выше свойствами.
Опишем
схему алгоритма
Адлемана - Ленстры
для проверки
простоты
:
1) выбираются
различные
простые числа
и различные
простые нечётные
такие, что
1) для каждого
все простые
делители числа
содержатся
среди
и
не делятся на
квадрат простого
числа;
1)
.
для каждой пары выбранных чисел
,
проводятся
тесты, подобные
сравнению из
теоремы 3. Если
не удовлетворяет
какому-либо
из
этих тестов - оно составное. В противном случаеопределяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители
.
А именно, каждый
простой делитель
числа
должен удовлетворять
сравнению вида
,
.
4) проверяется,
содержит ли
найденное
множество
делители
.
Если при этом
делители не
обнаружены,
утверждается,
что
- простое
число.
Если число
составное, оно
обязательно
имеет простой
делитель
,
меньший
,
который сам
содержится
среди возможных
остатков. Именно
на этом свойстве
основано применение
пункта 4) алгоритма.
Сумма Якоби

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

связывающее
суммы Гаусса
с суммами Якоби
и позволяющее
переписать
сравнение
теоремы 3 в терминах
сумм Якоби.
Так. при
и
соответствующее
сравнение,
справедливое
для простых
,
отличных от
2,3,7, принимает
вид