|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[249] Рис. 33.7 33.7 р-эвристика Полларда. (а) Последовательность хг1 = (xj - 1) mod 1387 с начальным элементом х\ = 2. (Разложение: 1387 = 19 • 73.) Жирные стрелки соответствуют шагам цикла, выполняемым до нахождения делителя 19. (После этого выполнение процедуры прекращается - но на рисунке показан весь р-цикл.) Серым цветом показаны последовательные значения переменной у. Делитель 19 обнаруживается при сравнении у = 63 с х7 = 177: НОД(63 - 177, 1387) = 19. (Ь) Та же самая последовательность по модулю 19. По этому модулю упомянутые выше числа х7 = 177 и у = 63 сравнимы, (с) Та же последовательность по модулю 73 так что можно опустить индекс г и использовать одну переменную х для хранения текущего члена последовательности). Переменная к последовательно принимает значения 2,4,8,... (строки 4 и 13), когда значение г доходит до текущего значения к, значение жг- запоминается в переменной у, а переменная к увеличивается вдвое. Таким образом, у последовательно принимает значения х\, х2, х4, х$,... В строках 8-10 мы пытаемся найти делитель числа га, используя два члена последовательности - текущее значение жг- и сохранённое значение у. Эта попытка удачна, если число d = gcd(y - Xi,n) отлично от 1 и от га (проверка выполняется в строке 9). Эти действия на первый взгляд выглядят странно, но по крайней мере легко видеть, что процедура Pollard-Rho никогда не выдаёт неправильных ответов: уж если она чего напечатала, значит, это нетривиальный делитель га. Вопрос только в том, напечатает ли она хоть что-то. Сейчас мы приведём некоторые неформальные аргументы в пользу того, что если число га имеет нетривиальный делитель s, то есть шансы найти его после y/s проходов. (Напомним, что у составного числа га есть делитель, не превосходящий у/п, так что ожидаемое число итераций можно оценить как -(/га. Вот обещанные неформальные аргументы. Для начала заметим, что последовательность (33.49), начиная с какого-то места, становится периодической. (В самом деле, возможностей конечное число, так что должно встретиться повторение, а дальше уже всё пойдёт по циклу, так как следующий член последовательности зависит только от предыдущего.) Поэтому последовательности можно изобразить в виде окружности с хвостиком (рис. 33.7): окружность соответствует периодической части последовательности, а хвостик - допериодической. (Эта картинка напоминает греческую букву р, поэтому метод и называется /-эвристикой.) Что можно сказать о длине периода для случайно выбранного х\1 Некоторая (пусть и безосновательная) оценка может быть получена так. Представим себе, что каждое жг- выбирается случайно и не зависит от предыдущих; сколько шагов пройдёт до первого повторения? (Конечно, предположение о случайности жг- абсурдно - каждый элемент есть функция предыдущего - но преобразование ж н-т- ж2 - 1 достаточно сложно, и с большой натяжкой его можно уподобить случайному перемешиванию.) Итак, сколько шагов пройдёт до первого повторения? Эту задачу мы уже рассматривали под названием парадокса с днями рождения (раздел 6.6.1), где отмечали, что среднее количество членов последовательности до первого повтора имеет порядок 0(у/га). Нас будут, впрочем, интересовать оценки длины периода не по модулю п, а по модулю делителей п. Пусть s - некоторый делитель п, для которого gcd(s,ra/s) = 1 (например, выделим степени некоторого одного простого множителя в разложении п на множители). Посмотрим на остатки от деления чисел жг- на число s. Эта последовательность ж = жг- mod s также можно рассматривать как заданную рекуррентным соотношением xi+1 = (xf - 1) (mods),(33.50) поскольку переход от модуля п к модулю s определён корректно (при s п) и перестановочен с возведением в квадрат и вычитанием единицы. Повторив приведённое выше вероятностное рассуждение, мы придём к заключению, что последовательность (ж) становится периодичной за 0(y/s) шагов. Можно ожидать, что в последовательности (ж) повторение появится раньше, так как сравнимость по модулю п - более сильное условие, чем сравнимость по модулю s. (На рис. 33.7 как раз такой случай и показан.) Теперь объясним, как используется переменная у. Пусть мы хотим найти повторяющиеся члены в последовательности (жг). Для этого не нужно сравнивать каждый член с каждым - вместо этого можно запоминать члены х\, х2, х4, х$,... и сравнивать другие члены последовательности с ними, ища повторений. При этом, конечно, мы не гарантируем, что обнаружим самую раннюю пару повторяющихся членов. Но поскольку повторение, раз случившись, далее идёт по циклу, мы его не пропустим. При этом нам придётся просмотреть больше членов последовательности, чем если бы мы сравнивали все пары, но ненамного (не более чем в константу раз). Процедура Pollard-Rho сравнивает текущее значение жг- с запомненным значением у - но вместо того, чтобы проверять их равенство (и тем самым искать повторения в последовательности (жг)) вычисляет наибольший общий делитель их разности и числа п. Смысл этого в том, что тем самым можно уловить цикл в последовательности ж - если Xi и у сравнимы по модулю s, то наибольший общий делитель жг- - у и п будет кратен s, и если только он не окажется равным п, то дело сделано - мы нашли нетривиальный делитель числа п. (Заметим ещё, что число s используется только в наших рассуждениях, не встречаясь в программе.) Всё может быть не так гладко, как мы описали, по двум причинам. Во-первых, наши оценки для числа шагов - всего лишь прикидкии, и алгоритм может проработать намного дольше, прежде чем будет найден общий делитель. Во-вторых, обнаруженный делитель, кратный s, может оказаться равным п и, следовательно, бесполезным. Такое возможно: пусть, например, п = pq, где р и q просты, и пусть последовательности (жг- mod р) и (жг- mod q) имеют одинаковые по длине периодические и допериодические части. Тогда повторения по модулю р совмещены с повторениями по модулю q, и в результате будет обнаруживаться общий делитель п. Обе эти возможности редко встречаются на практике. В крайнем случае можно изменить формулу, порождающую рекуррентную последовательность, положив, например, жг 1 равным (жг-2 - с) mod п. В качестве значения с не следует брать 0 и 2 (не будем сейчас объяснять, почему); другие значения вполне приемлемы. Конечно, наш анализ весьма приблизителен, так как поскольку числа Xi не являются случайными - но на практике процедура работает хорошо, являясь одним из наиболее эффективных методов поиска небольших делителей больших целых чисел: оценка yfs на число операций зависит от величины делителя, а не от величины самого числа. При работе с /3-битовым числом п мы ищем множители до у/п, то есть размера не более /3/2, и ожидаемое число арифметических операций имеет порядок га1/4 = 2/4 (что даёт порядка га1/,4/33 = 2/4/33 битовых операций. Упражнения 33.9-1 Пользуясь рис. 33.7(a), определите, в какой моментэ процедура Pollard-Rho напечатает делитель 73 числа 1387. 33.9-2 Пусть задана функция / : Ъп -> Ъп и значение жо G Ъп. Определим последовательность Ж1,Ж2,... соотношением жг- = f(xi-\). Обозначим через и длину периодической части последовательности, а через t - длину допериодической части. Предложите эффективный алгоритм нахождения t и и. Оцените время его работы. 33.9-3 Через сколько шагов можно ожидать, что процедура Pollard-Rho обнаружит делитель вида ре, где р - простое число, а е > 1? 33.9-4* Процедура Pollard-Rho на каждом шаге вычисляет наибольший общий делитель. Можно пытаться ускорить работу процедуры так: перемножить несколько соседних членов последовательности (жг), и вычислить наибольший общих делитель их произведения и числа у. Разработайте соответствующую процедуру и объясните, почему она будет работать. Сколько соседних членов стоит брать при работе с /3-битовыми числами? Задачи. |
Среды: 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 | ||