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