Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Преимущество этой модификации состоит в том, что при каждом к вычисляется лишь один НОД, а недостаток — в том, что алгоритм может пропустить первый такой момент ко, что НОД (хко — Xj0,n) = г > 1 при некотором J0 < Аго ¦ Однако довольно быстро пара элементов xk,Xj, разность которых имеет нетривиальный общий множитель с п, все же будет обнаружена. А именно, пусть j = 2h+1 - 1 и к = j + (k0—j0). Тогда j — максимальное (/і+1)-разрядное число, к состоит
из h + 2 разрядов, при этом НОД (хк — Xj,n) > 1. Заметим, что к < 2h+2 _ 4 _2л ^ 4^
Пример 2. Вернемся к примеру 1, но теперь будем сравнивать каждое хк лишь с тем Xj, для которого j является наибольшим из
меньших к чисел вида 2h — 1. Для п = 91, f(x) = х2 + 1, х0 = 1 имеем Х\ = 2, X2 = 5, X3 = 26, как и выше, и = 40 (так как 262 + 1 = 40 (mod 91)). Следуя описанному выше алгоритму, находим
формулу для суммы первых / натуральных чисел, получаем
158
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
делитель числа п, вычисляя НОД (х4 - x3,n) = НОД (14,91) = 7.
Пример 3. Разложить на множители число 4087, используя /(х) = X +х+1ихо = 2.
Решение. Проводим вычисления в следующем порядке:
X1 = /(2) = 7; НОД (X1 - х0, п) = НОД (7 - 2,4087) = 1;
х2 = /(7) = 57; НОД (х2 - X1, n) = НОД (57 - 7,4087) = 1; X3 = /(57) = 3307; НОД (х3 - X1, n) = НОД (3307 - 7,4087) = 1;
X4 = /(3307) = 2745 (mod 4087); НОД (х4 - х3, n) = НОД (2745 - 3307,4087) = 1;
X5 = /(2745) = 1343 (mod 4087); НОД (х5 - х3, n) = НОД (1343 - 3307,4087) = 1;
X6 = /(1343) = 2626 (mod 4087); НОД (х6 - Z3, n) = НОД (2626 - 3307,4087) = 1;
X7 = /(2626) = 3734 (mod 4087); НОД (х7 - х3, n) = НОД (3734 - 3307,4087) = 61.
Итак, мы получили 4087 = 61 ¦ 67. Разложение найдено.
Предложение V.2.2. Пусть п — нечетное составное целое число иг— его нетривиальный делитель, не превосходящий у/п (т. е. r\n, 1 < г < у/п;/мы хотим найти такое г). Пусть пара (f,x0), состоящая из многочлена f с целыми коэффициентами и начального значения хо, выбрана так, что ведет себя подобно «случайной» паре (/,Xo) б смысле предложения V. 2. 1 (/ отображает Z/rZ в себя, Xq — целое число). Тогда ро-метод выявляет делитель г за 0(^/п log п) двоичных операций с высокой степенью вероятности. Точнее, существует такая константа С, что для любого вещественного положительного числа А вероятность того, что ро-метод не найдет нетривиального делителя числа п за Сл/\^/пlog п двоичных операций, меньше е Л.
Доказательство. Пусть C1 — такая константа, что НОД (у — z,n) можно вычислить за C1IOg п двоичных операций, если у, z (см. §1.3). Пусть C2 — такая константа, что наименьший неотрицательный вычет из /(х) по модулю п можно вычислить за C2 log п двоичных операций, если х < п (см. §1.1). Если к0 — первый из индексов, для которых существует Jo < K0 со свойством X^0 = xj0 (mod г), то ро-метод в том виде, как он был описан выше, позволяет найти г на к-м шаге, где к < 4&0. (Строго говоря, может
§ 2. po-метод
159
случиться, что НОД (хк - Xj,n) > г, т.е. НОД ((хк - Xj)/r,n/r) > 1. Однако вероятность случайно выбрать целое число, не взаимно простое с n/r, мала, особенно если п — произведение небольшого количества больших простых чисел. Поэтому мы пренебрежем этой возможностью, которая, в худшем случае, потребовала бы увеличения константы в предположениях предложения V. 2. 2.)
Таким образом, число двоичных операций, необходимых для на-
і 3 2
хождения г, ограничено величиной Ak0(Ci log п + C2 log п). Согласно предложению V.2.1 вероятность того, что к0 > 1 + V2Ar, меньше е~ . Если &о ^ 1 + \/2Лг, то число двоичных операций, необходимых для нахождения г, оценивается (с учетом того, что г < \/п) величиной
4(1+VSArO(C1 log3 TiArC2 log2 n) < 4(1 + V^VXVn-)(C1 log3 TiA-C2 log2 n).
Если мы выберем С несколько больше, чем 4V^(C1 +C2) (позаботившись о прибавлении 1), получим, что, как и утверждалось, делитель г будет найден за C\f\-sfn log п двоичных операций, если только мы не сделаем неудачного выбора пары (/, Xq), вероятность
-А
чего меньше е
Замечания. 1. Основное предположение, лежащее в основе ро-метода, состоит в том, что можно найти многочлены, которые ведут себя подобно случайным отображениям в смысле предложения V. 2.1. Этого доказано не было. Однако практический опыт разложения чисел ро-методом позволяет предположить, что «случайный» многочлен ведет себя подобно случайному отображению и что есть очень простые многочлены (чаще всего используется /(х) = X2 + 1), обладающие этим свойством «случайности».
2. Согласно предложению V.2.2, если мы выберем Л достаточно большим, чтобы быть уверенными в успехе (например, выберем Л = 9, тогда е Л яа 0,0001), то мы почти наверное разложим число п за 3CV" log3 п двоичных операций.
УПРАЖНЕНИЯ
В упражнениях 1-4 применить ро-метод с указанными /(х) и Xq для разложения заданного числа п. В каждом случае сравнивать хд. лишь с Xj, для которого j = 2h — 1, если к является (h + 1)-разрядным двоичным числом.
1. X2 - 1, x0 = 2, п = 91.
2. x2 + 1, x0 = 1, n = 8051.
