|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[19] Тест Ферма Тест на простоту с порядком роста 0(log n) основан на утверждении из теории чисел, известном как Малая теорема Ферма.45 Малая теорема Ферма: Если n - простое число, а а - произвольное целое число меньше, чем n, то а, возведенное в n-ю степень, равно а по модулю n. (Говорят, что два числа равны по модулю n (congruent modulo n), если они дают одинаковый остаток при делении на n. Остаток от деления числа а на n называется также остатком а по модулю n (remainder of а modulo n) или просто а по модулю n.) Если n не является простым, то, вообще говоря, большинство чисел а < n не будут удовлетворять этому условию. Это приводит к следующему алгоритму проверки на простоту: имея число n, случайным образом выбрать число а < n и вычислить остаток от ап по модулю n. Если этот остаток не равен а, то n определенно не является простым. Если он равен а, то мы имеем хорошие шансы, что n простое. Тогда нужно взять еще одно случайное а и проверить его тем же способом. Если и оно удовлетворяет уравнению, мы можем быть еще более уверены, что n простое. Испытывая все большее количество а, мы можем увеличивать нашу уверенность в результате. Этот алгоритм называется тестом Ферма. Для реализации теста Ферма нам нужна процедура, которая вычисляет степень числа по модулю другого числа: (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) Эта процедура очень похожа на fast-expt из раздела 1.2.4. Она использует последовательное возведение в квадрат, так что число шагов логарифмически 46 растет с увеличением степени.46 45Пьер де Ферма (1601-1665) считается основателем современной теории чисел. Он доказал множество важных теорем, однако, как правило, он объявлял только результаты, не публикуя своих доказательств. Малая теорема Ферма была сформулирована в письме, которое он написал в 1640-м году. Первое опубликованное доказательство было дано Эйлером в 1736 г. (более раннее, идентичное доказательство было найдено в неопубликованных рукописях Лейбница). Самый знаменитый результат Ферма, известный как Большая теорема Ферма, был записан в 1637 году в его экземпляре книги Арифметика (греческого математика третьего века Диофанта) с пометкой «я нашел подлинно удивительное доказательство, но эти поля слишком малы, чтобы вместить его». Доказательство Большой теоремы Ферма стало одним из самых известных вопросов теории чисел. Полное решение было найдено в 1995 году Эндрю Уайлсом из Принстонского университета. 46Шаги редукции для случаев, когда степень больше 1, основаны на том, что для любых целых чисел x, y и m мы можем найти остаток от деления произведения x и y на m путем отдельного вычисления остатков x по модулю m, y по модулю m, перемножения их, и взятия остатка по модулю m от результата. Например, в случае, когда e четно, мы можем вычислить остаток be/2 по модулю m, возвести его в квадрат и взять остаток по модулю m. Такой метод полезен потому, что с его помощью мы можем производить вычисления, не используя чисел, намного больших, чем m. (Сравните с упражнением 1.25.) Тест Ферма производится путем случайного выбора числа а между 1 и n - 1 включительно и проверки, равен ли а остаток по модулю n от n-ой степени а. Случайное число а выбирается с помощью процедуры random, про которую мы предполагаем, что она встроена в Scheme в качестве элементарной процедуры. Random возвращает неотрицательное число, меньшее, чем ее целый аргумент. Следовательно, чтобы получить случайное число между 1 и n- 1, мы вызываем random с аргументом n - 1 и добавляем к результату 1: (define (fermat-test n) (define (try-it a) (= (expmod a n n) a)) (try-it (+ 1 (random (- n 1))))) Следующая процедура прогоняет тест заданное число раз, как указано ее параметром. Ее значение истинно, если тест всегда проходит, и ложно в противном случае. (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false))) Вероятностные методы Тест Ферма отличается по своему характеру от большинства известных алгоритмов, где вычисляется результат, истинность которого гарантирована. Здесь полученный результат верен лишь с какой-то вероятностью. Более точно, если n не проходит тест Ферма, мы можем точно сказать, что оно не простое. Но то, что n проходит тест, хотя и является очень сильным показателем, все же не гарантирует, что n простое. Нам хотелось бы сказать, что для любого числа n, если мы проведем тест достаточное количество раз и n каждый раз его пройдет, то вероятность ошибки в нашем тесте на простоту может быть сделана настолько малой, насколько мы того пожелаем. К сожалению, это утверждение неверно. Существуют числа, которые «обманывают» тест Ферма: числа, которые не являются простыми и тем не менее обладают свойством, что для всех целых чисел а < n ап равно а по модулю n. Такие числа очень редки, так что на практике тест Ферма вполне надежен.47 Существуют варианты теста Ферма, которые обмануть невозможно. В таких тестах, подобно методу Ферма, проверка числа n на простоту ведется путем выбора случайного числа а < n и проверки некоторого условия, зависящего от n и а. (Пример такого теста см. в упражнении 1.28.) С другой стороны, в отличие от теста Ферма, можно доказать, что для любого n условие не выполняется для большинства чисел а < n, если n не простое. Таким образом, если n проходит тест для какого-то случайного а, шансы, что n простое, уже больше 47Числа, «обманывающие» тест Ферма, называются числами Кармайкла (Carmichael numbers), и про них почти ничего неизвестно, кроме того, что они очень редки. Существует 255 чисел Кармайкла, меньших 100 000 000. Несколько первых - 561, 1105, 1729, 2465, 2821 и 6601. При проверке на простоту больших чисел, выбранных случайным образом, шанс наткнуться на число, «обманывающее» тест Ферма, меньше, чем шанс, что космическое излучение заставит компьютер сделать ошибку при вычислении «правильного» алгоритма. То, что по первой из этих причин алгоритм считается неадекватным, а по второй нет, показывает разницу между математикой и техникой. половины. Если n проходит тест для двух случайных а, шансы, что n простое, больше, чем 3 из 4. Проводя тест с большим количеством случайных чисел, мы можем сделать вероятность ошибки сколь угодно малой. Существование тестов, для которых можно доказать, что вероятность ошибки можно сделать сколь угодно малой, вызвало большой интерес к алгоритмам такого типа. Их стали называть вероятностными алгоритмами (probabilistic alorithms). В этой области ведутся активные исследования, и вероятностные алгоритмы удалось с успехом применить во многих областях. 48 Упражнение 1.21. С помощью процедуры smallest-divisor найдите наименьший делитель следующих чисел: 199, 1999, 19999. Упражнение 1.22. Большая часть реализаций Лиспа содержат элементарную процедуру runtime, которая возвращает целое число, показывающее, как долго работала система (например, в миллисекундах). Следующая процедура timed-prime-test, будучи вызвана с целым числом п, печатает п и проверяет, простое ли оно. Если п простое, процедура печатает три звездочки и количество времени, затраченное на проверку. (define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) Используя эту процедуру, напишите процедуру search-for-primes, которая проверяет на простоту все нечетные числа в заданном диапазоне. С помощью этой процедуры найдите наименьшие три простых числа после 1000; после 10 000; после 100 000; после 1 000 000. Посмотрите, сколько времени затрачивается на каждое простое число. Поскольку алгоритм проверки имеет порядок роста Q(y/n), Вам следовало бы ожидать, что проверка на простоту чисел, близких к 10 000, занимает в vTo раз больше времени, чем для чисел, близких к 1000. Подтверждают ли это Ваши замеры времени? Хорошо ли поддерживают предсказание л/n данные для 100 000 и 1 000 000? Совместим ли Ваш результат с предположением, что программы на Вашей машине затрачивают на выполнение задач время, пропорциональное числу шагов? 48Одно из наиболее впечатляющих применений вероятностные алгоритмы получили в области криптографии. Хотя в настоящее время вычислительных ресурсов недостаточно, чтобы разложить на множители произвольное число из 200 цифр, с помощью теста Ферма проверить, является ли оно простым, можно за несколько секунд. Этот факт служит основой предложенного в Rivest, Shamir, and Adleman 1977 метода построения шифров, которые «невозможно» взломать. Полученный алгоритм RSA (RSA algorithm)стал широко используемым методом повышения секретности электронных средств связи. В результате этого и других связанных событий исследование простых чисел, которое раньше считалось образцом «чистой» математики, изучаемым исключительно ради самого себя, теперь получило важные практические приложения в таких областях, как криптография, электронная передача денежных сумм и хранение информации. |
Среды: 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 | ||