Применение алгоритма RSA для шифрования потоков данных - (диплом)
p>Обсудим теперь некоторые теоретические вопросы, возникающие в связи с нахождением числа, удовлетворяющего неравенствам , и такого, что - простое число. Прежде всего, согласно теореме Дирихле, доказанной еще в 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, принимает вид ,
где и - некоторый корень кубический из 1.
