|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[5] тех пор. пока не будет найдено число N. выдержавшее испытания алгоритмом 5 достаточно много раз. В этом случае появляется надежда на то. что N - простое число, и следует попытаться доказать простоту с помошью тестов теоремы 2. Для этого можно случайным образом выбирать число а. 1 < а < N. и проверять для него выполнимость соотношений Если при выбранном а эти соотношения выполняются, то. согласно следствию из теоремы 2. можно утверждать, что число N простое. Если же эти условия нарушаются, нужно выбрать другое значение а и повторять эти операции до тех пор. пока такое число не будет обнаружено. Предположим, что построенное число N действительно является простым. Зададимся вопросом, сколь долго придётся перебирать числа а. пока не будет найдено такое, для которого будут выполнены условия (12). Заметим, что для простого числа N первое условие (12). согласно малой теореме Ферма, будет выполняться всегда. Те же числа а. для которых нарушается второе условие (12). удовлетворяют сравнению aR = 1 (mod N). Как известно, уравнение xR = 1 в поле вычетов Гдг имеет не более R решений. Одно из них х = 1. Поэтому на промежутке 1 < а < N имеется не более R - 1 чисел, для которых не выполняются условия (12). Это означает, что. выбирая случайным образом числа а на промежутке 1 < а < N. при простом N можно с вероятностью большей, чем 1 - 0(S~1). найти число а. для которого будут выполнены условия теоремы 2. и тем доказать, что N действительно является простым числом. Заметим, что построенное таким способом простое число N будет удовлетворять неравенству N > S2. т. е. будет записываться вдвое большим количеством цифр, чем исходное простое число S. Заменив теперь число S на найденное простое число N и повторив с этим новым S все указанные выше действия, можно построить ешё большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз. можно построить простые числа нужной величины. Обсудим теперь некоторые теоретические вопросы, возникаюшие в связи с нахождением числа R. удовлетворяюшего неравенствам S R 45 + 2. и такого, что N = SR +1 - простое число. Прежде всего, согласно теореме Дирихле, доказанной ешё в 1839 г.. прогрессия 2Sn + 1, п = 1,2.3.... содержит бесконечное количество простых чисел. Нас инте- 1 (mod N). (ан - 1. N) = 1. ресуют простые числа, лежащие недалеко от начала прогрессии. Опенка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю. В. Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии 2Sn + 1 не превосходит SG. где С - некоторая достаточно большая абсолютная постоянная. В предположении справедливости расширенной гипотезы Римана можно доказать. [13. стр. 272]. что наименьшее такое простое число не превосходит с(е) 52+е при любом положительном е. Таким образом, в настоящее время никаких теоретических гарантий для сушествования простого числа N = SR+ 1. 5 R 45 + 2 не существует. Тем не менее опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии встречаются достаточно близко к её началу. Упомянем в этой связи гипотезу о сушествовании бесконечного количества простых чисел q с условием, что число 2q + 1 также простое, т. е. простым является уже первый член прогрессии. Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором R число N = 5i?+ 1 составное, можно следующее значение R взять равным R + 2 и действовать так далее, пока не будет найдено простое число N. И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число N. Перебор чисел R до того момента, как мы наткнемся на простое число N окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами рп и p„+i в натуральном ряде доказано лишь, что Рп+1 - Рп = О I рп ), что. конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера (1936 г.). что рп+1-рп = О (In2 рп). дающая вполне приемлемую опенку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно. В качестве итога обсуждения в этом пункте подчеркнём следующее: если принять на веру, что наименьшее простое число, а также расстояние между соседними простыми числами в прогрессии 2Sn + 1 при 5 п 45 + 2 оцениваются величиной О (In2 5). то описанная схема построения больших простых чисел имеет полиномиальную опенку сложности. Кроме того, несмотря на отсутствие теоретических оценок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно. На обычном персональном компьютере без особых затрат времени строятся таким способом простые числа порядка 10300. Конечно, способ конструирования простых чисел для использования в схеме RSA должен быть массовым, а сами простые числа должны быть в каком-то смысле хорошо распределёнными. Это вносит ряд дополнительных осложнений в работу алгоритмов. Впрочем, описанная схема допускает массу вариаций. Все эти вопросы рассматриваются в статье [14]. Наконец, отметим, что существуют методы построения больших простых чисел, используюшие не только простые делители N - 1. но и делители чисел N+l. N2-\-l. N2 ±N +1. В основе их лежит использование последовательностей целых чисел, удовлетворяюших линейным рекуррентным уравнениям различных порядков. Отметим, что последовательность ап, члены которой присутствуют в формулировке малой теоремы Ферма, составляет решение рекуррентного уравнения первого порядка ип+\ = аип. и0 = 1. 5. Как проверить большое число на простоту Есть некоторое отличие в постановках задач предыдущего и настоящего пунктов. Когда мы строим простое число N. мы обладаем некоторой дополнительной информацией о нем. возникаюшей в процессе построения. Например, такой информацией является знание простых делителей числа N - 1. Эта информация иногда облегчает доказательство простоты N. В этом пункте мы предполагаем лишь, что нам задано некоторое число N. например, выбранное случайным образом на каком-то промежутке, и требуется установить его простоту, или доказать, что оно является составным. Эту задачу за полиномиальное количество операций решает указанный в п. 3 алгоритм Миллера. Однако, справедливость полученного с его помошью утверждения зависит от недоказанной расширенной гипотезы Римана. Если число N выдержало испытания алгоритмом 5 для 100 различных значений параметра а. то. по-видимому, можно утверждать, что оно является простым с вероятностью большей, чем 1 - 4-100. Эта вероятность очень близка к единице, однако всё же оставляет некоторую тень сомнения на простоте числа N. В дальнейшем в этом пункте мы будем считать, что заданное число N является простым, а нам требуется лишь доказать это. В настоящее время известны детерминированные алгоритмы различной сложности для доказательства простоты чисел. Мы остановимся подробнее на одном из них. предложенном в 1983 г. в совместной работе |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||