Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 75

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 125 >> Следующая


Метод пробных делений на простые числа, меньшие у/п, может потребовать более 0(\/п) двоичных операций. Простейший алгоритм, работающий существенно быстрее, — это «ро-метод» факторизации Полларда (называемый также «методом Монте-Карло»).

Первый шаг ро-метода заключается в выборе легко вычислимого отображения кольца Z/nZ в себя, а именно, простого многочлена с целыми коэффициентами, например, Дх) = х + 1. Затем выбираем некоторое конкретное значение х0 (это может быть 1 или 2 или случайно порожденное целое число) и последовательно вычисляем итерации х\ = f{xo), Х2 = ДДяо)), хз = ДДД^о))) и т.д. Таким образом, мы полагаем

xj+i = f(*j), І = 0,1,2,...

После этого производится сравнение различных Xj с целью найти два, принадлежащих различным классам вычетов по модулю п, но одному классу вычетов по модулю некоторого делителя числа п. Как только такие Xj, Xk найдены, сразу находим собственный делитель числа п как НОД (xj — Xk, п).

Пример 1. Разложим на множители число 91, взяв Дх) = X +1, X0 = 1. Имеем X1 = 2, X2 = 5, X3 = 26 и т. д. Находим НОД (х3 — х2, п) = НОД (21,91) = 7, т. е. 7 — делитель. Конечно, этот пример тривиален: делитель 7 быстрее было найти пробным делением.

В ро-методе важно выбрать многочлен Дх), отображающий Z/nZ в себя нерегулярным, «случайным» образом. Так, вскоре мы убедимся, что Дх) должен не быть линейным многочленом и должен не порождать взаимно однозначное отображение.

156

ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ

Предположим теперь, что /(х) — «случайное» отображение Z/nZ в себя, и оценим, как долго нам придется ждать появления двух таких итераций Xj ж хк, что Xj - хк и п имеют нетривиальный общий делитель. Для этого для фиксированного (но не известного нам) делителя г числа п найдем типичную (б среднем по всем отображениям Z/nZ в себя и по всем значениям Xq) величину первого такого значения к, что хк = Xj (mod г) при некотором j < к. Иными словами, мы рассматриваем f(x) как отображение Z/rZ в себя и интересуемся, сколько

ПОТребуеТСЯ ИТераЦИЙ до ВОЗНИКНОВеНИЯ ПерВОГО ПОВТОреНИЯ Xj = хк

в Ъ/тЪ.

Предложение V. 2.1. Пусть S — множество из г элементов. Для отображения f множества S в себя и элемента Xq є S полагаем Xj+i = f(xj), j = 0,1,2,... Пусть А — положительное вещественное число и пусть 1=1 + [\/2Лг]. Тогда доля пар (/, х0), для которых все XQjX1,... ,Xi различны (где f пробегает все отображения из S в S, a X0 пробегает все элементы S), меньше е

Доказательство. Общее число рассматриваемых пар равно rr+1, так как существует всего г вариантов выбора для х0 и для каждого из г различных элементов х Є S имеется г вариантов выбора /(х). Сколько существует таких пар (/,х0), для которых х0,хг,... ,X1 различны? Значение х0 можно выбрать г способами, значение /(х0) можно выбрать г - 1 способами (так как f(x0) ф х0), значение /(X1) можно выбрать г - 2 способами и т. д., пока функция / не будет определена для всех Xq, хх,... ,xi-i- Значения функции / на остальных значениях аргумента произвольны /и имеется гТ ' вариантов их выбора. Поэтому общее число таких способов выбора х0 и задания функции f(x), что все X0,Xi,... ,Xi различны, равно

rr-lll(r-j),

j=o

а доля тех пар, которые обладают указанным свойством (отношение

г+1 \

приведенного выражения кг ), равна

'-'"П<'-я = П(і-;)-

j=o j=i 4 у

Предложение утверждает, что логарифм этого выражения меньше -Л (где 1=1 + [V^Ar]). Чтобы доказать это, возьмем логарифм произведения в правой части и используем неравенство log(l - х) < -х при О < X < 1 (на геометрическом языке это означает, что логарифмическая кривая лежит ниже касательной к ней в точке (1,0)). Используя

§ 2. PO-МЕТОД 157

ЧП(і-;))<?-

что и требовалось показать. Предложение доказано.

Предложение V. 2. 1 дает оценку для вероятного времени работы ро-метода при условии, что выбранный многочлен ведет себя как «случайное» отображение Z/VZ в себя. Прежде чем обсуждать эту оценку, мы изложим более эффективную версию ро-метода.

Напомним, что ро-метод состоит в последовательном вычислении хк = f(xk_i) и сравнении хк с ранее полученными Xj до тех пор, пока не найдется пара с НОД (хк - Xj, п) = г > 1. Однако с ростом к вычисление НОД (хк - Xj,n) для всех j < к становится очень трудоемким. Покажем теперь, как надо действовать, чтобы при каждом к вычислять лишь один НОД. Сначала заметим, что если при некоторых к0, J0 для делителя г числа п выполняется сравнение хко = Xj0 (mod г), то хк = Xj (mod г) для любой последующей пары индексов j, к, имеющих ту же разность: к — j = к0 — J0 = т- Чтобы убедиться в этом, достаточно к сравнению хко = Xj0 (mod г) применить т раз многочлен /.

Опишем теперь работу алгоритма. Последовательно вычисляя хк, на каждом шаге делаем следующее. Пусть к является (/і + 1)-разрядным целым числом в двоичной системе счисления, т.е. 2 ^ к ^ 2h+l. Пусть j — наибольшее число из h двоичных разрядов: j = 2h - 1. Сравниваем хк с Xj, т.е. вычисляем НОД (хк — Xj,n). Если в результате получаем нетривиальный делитель числа п, то останавливаемся, если нет, то переходим к к + 1.
Предыдущая << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed