|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[4] делится на N. Обращение этого свойства можно использовать, чтобы отличать составные числа от простых. Пусть N - нечётное составное число. N - 1 = 2s t, где t нечётно. Назовем целое число а. 1 < а < N. «хорошим» для N. если нарушается одно из двух условий: а) N не делится на а: /3) а* = 1 (mod N) или существует целое к, 0 к < s, такое, что а24 = -1 (mod N). Из сказанного ранее следует, что для простого числа N не существует хороших чисел а. Если же N составное число, то. как доказал Рабин. их существует не менее (А - 1). Теперь можно построить вероятностный алгоритм, отличающий составные числа от простых. 5. Алгоритм, доказывающий непростоту числа. 1)Выберем случайным образом число а. 1 < а < N. и проверим для этого числа указанные выше свойства а) и (3). 2)Если хотя бы одно из них нарушается, то число N составное. 3)Если выполнены оба условия а) и (3). возвращаемся к шагу 1. Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей 4-1. А вероятность не определить его после к повторений не превосходит 4~к. т. е. убывает очень быстро. Миллер предложил детерминированный алгоритм определения составных чисел, имеющий сложность 0(ln3 N), однако справедливость его результата зависит от недоказанной в настоящее время так называемой расширенной гипотезы Римана. Согласно этому алгоритму достаточно проверить условия а) и /3) для всех целых чисел а, 2 а 70 In2 А. Если при каком-нибудь а из указанного промежутка нарушается одно из условий а) или 13), число N составное. В противном случае оно будет простым или степенью простого числа. Последняя возможность, конечно, легко проверяется. Напомним некоторые понятия, см. [5]. необходимые для формулировки расширенной гипотезы Римана. Они понадобятся нам и в дальнейшем. Пусть то 2 - целое число. Функция \ -> С называется характером Дирихле по модулю то. или просто характером, если эта функция периодична с периодом то. отлична от нуля только на числах, взаимно простых с то. и мультипликативна, т. е. для любых целых и, v выполняется равенство x{uv) = x{u)x{v)- Для каждого то существует ровно (f(m) характеров Дирихле. Они образуют группу по умножению. Единичным элементом этой группы является так называемый главный характер хо-, равный 1 на всех числах, взаимно простых с то. и 0 на остальных целых числах. Порядком характера называется его порядок как элемента мультипликативной группы характеров. С каждым характером может быть связана так называемая L-функ-ния Дирихле - функция комплексного переменного s, определённая ря- > 1 и может быть аналитически продолжена на всю комплексную плоскость. Следующее соотношение L(s,xo) = C(s) Jf(l ~ P~s) связывает L- функцию, отвечающую главному характеру, с дзета-функцией Римана ные нули всех L-функний Дирихле, расположенные в полосе 0 < Res < 1, лежат на прямой Res = \. В настоящее время не доказана даже простейшая форма этой гипотезы - классическая гипотеза Римана. утверждающая такой же факт о нулях дзета-функции. В 1952 г. Анкени с помощью расширенной гипотезы Римана доказал, что для каждого простого числа q существует квадратичный невычет а. удовлетворяющий неравенствам 2 а 70 In2 q. Константа 70 была сосчитана позднее. Именно это утверждение и лежит в основе алгоритма Миллера. В 1957 г. Берджесс доказал существование такого невычета без использования расширенной гипотезы Римана. но с худшей оценкой 2 а q4Se -\-е. справедливой при любом положительном е и q. большем некоторой границы, зависящей от е. Алгоритм Миллера принципиально отличается от алгоритма 5. так как полученное с его помощью утверждение о том. что число N - составное, опирается на недоказанную расширенную гипотезу Римана и потому может быть неверным. В то время как вероятностный алгоритм 5 даёт совершенно правильный ответ для составных чисел. Несмотря на отсутствие опенок сложности, на практике он работает вполне удовлетворительно. 4. Как строить большие простые числа Мы не будем описывать здесь историю этой задачи, рекомендуем обратиться к книге [7] и обзорам [10. 11]. Конечно же. большие простые числа можно строить сравнительно быстро. При этом можно обеспечить аналитична в области Res > C(s) V . 1> п=0 асширенная гипотеза Римана утверждает, что комплекс- их случайное распределение в заданном диапазоне величин. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма. Теорема 2. Пусть N. 5 - нечётные натуральные числа. N - 1 = = S R. причем для каждого простого делителя q числа 5 существует целое число а такое, что лг 1N-1 а = 1 (mod N), {а я -1.ЛГ) = 1.(10) Тогда каждый простой делитель р числа N удовлетворяет сравнению р = 1 (mod 25). Доказательство. Пусть р - простой делитель числа N. a q - некоторый делитель 5. Из условий (10) следует, что в поле вычетов ¥р справедливы соотношения aN~1 = 1. а V ф 1. а131 = 1.(11) Обозначим буквой г порядок элемента а в мультипликативной группе поля ¥р. Первые два из соотношений (11) означают, что q входит в разложение на простые множители числа г в степени такой же. как и в разложение N - 1, а последнее - что р - 1 делится на г. Таким образом, каждый простой делитель числа 5 входит в разложение р - 1 в степени не меньшей, чем в 5. так что р - 1 делится на 5. Кроме того, р - 1 четно. Теорема 2 доказана. Следствие. Если выполнены условия теоремы 2 и R 45 + 2, то N - простое число. Действительно, пусть N равняется произведению не менее двух простых чисел. Каждое из них. согласно утверждению теоремы 2. не меньше, чем 25 + 1. Но тогда (25 + 1)2 N = SR + 1 452 + 25 + 1. Противоречие и доказывает следствие. Покажем теперь, как с помошью последнего утверждения, имея большое простое число 5. можно построить сушественно большее простое число N. Выберем для этого случайным образом чётное число R на промежутке 5i? 45+ 2и положим N = SR + 1. Затем проверим число N на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем N некоторое количество раз с помошью алгоритма 5. Если при этом выяснится, что N - составное число, следует выбрать новое значение R и опять повторить вычисления. Так следует делать до |
Среды: 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 | ||