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

  • Просмотров 7965
  • Скачиваний 308
  • Размер файла 89
    Кб

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

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

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

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

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

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