Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Доказательство. Применим предложение V. 4. 2 при х = у/п. Тогда Ьг = bj — nCj (mod п), а это последнее число меньше 2\/п по абсолютной величине.
Предложение V. 4. 3 — ключевое для алгоритма цепных дробей. Оно показывает, что можно найти последовательность чисел bj, квадраты которых имеют малые вычеты по модулю п. Для этого нужно брать числители приближений при разложении \/п в цепную дробь. Заметим, что нам нужно находить не сами приближения, а только их числители 6,, и то лишь по модулю п. Поэтому быстрый рост числителей и знаменателей приближений не является препятствием. Нам никогда не придется работать с числами, большими п (при умножении чисел по модулю п).
Опишем теперь последовательно, как работает алгоритм цепных дробей. Он отличается от метода факторных баз из § 3 лишь использованием предложения V.4.3 вместо случайного выбора чисел 6,.
Алгоритм разложения на множители при помощи цепных дробей. Пусть п — целое число, которое нужно разложить на
178
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
множители. Все вычисления будем проводить по модулю п, т.е. произведения и суммы целых чисел будем приводить по модулю п к их наименьшему неотрицательному вычету (или к наименьшему абсолютному вычету в шаге 3). Вначале полагаем b_\ = 1, b0 = а0 = [л/п],
2 2
Xo = урп - о-о- Вычисляем 6о (mod п) (фактически 60 - п). Далее для г = 1,2,.. . последовательно выполняем следующие действия.
1) Полагаем Oj = [1/Xj-1] и затем х{ = \/хі_\ — аг-.
2) Полагаем 6j = OjOj-1 + bj_2 (приводим по модулю п).
3) Вычисляем bj (mod п). Проделав это для нескольких і, обращаем внимание на те из чисел на шаге 3, абсолютная величина которых представляется в виде произведения малых простых чисел. Пусть факторная база В состоит из -1 и простых чисел, которые встречаются более чем в одном из bi (mod п) (или входят только в одно из 6j (mod ті) в четной степени). Составляем список всех тех чисел bi (mod п), которые являются Б-числами, и соответствующих векторов ?j из нулей и единиц. Если возможно, находим подмножество векторов с нулевой суммой. Полагаем 6 = Г] 6г- (проводя вычисления по модулю п; произведение берется по подмножеству с = 0). Полагаем с = Y[p]}, где Pj — элементы из В (исключая — 1), и jj = j ^ etij (где сумма берется по тому же подмножеству индексов г, см. § 3). Если Ь ф ±с (mod п), то НОД (6 + с, п) — нетривиальный делитель п. Если b = ±с (mod п), то ищем другое подмножество индексов і, для которого ^ Ei = 0. Если невозможно найти такое подмножество индексов і, что ^T1 Ei = 0, то нужно продолжать, вычисляя новые ?j, 6j, bi (mod п) и при необходимости расширяя факторную базу В.
Замечание. Чтобы упростить вычисление с = Yl Pj1 > удобно для каждого Б-числа b\ (mod п) записывать вектор ojj = (..., аі;-,...), а не Ei, который представляет собой вектор а,-, приведенный по модулю 2.
Пример 2. Используем изложенный алгоритм для разложения 9073 на множители.
Решение. Вначале выпишем по порядку aj и Ь; (где 6j — наименьший неотрицательный вычет a^i-i +bj_2 по модулю п), а также наименьшие абсолютные вычеты bj (mod п):
0
1
2
3
4
95
3
1
26
2
95
286
381
1119
2619
-48
139
-7
87
-27
Рассматривая последнюю строку таблицы, мы видим, что в качестве В разумно взять множество {-1,2,3,7}. Тогда b\ (mod п) — В-
§ 4. МЕТОД ЦЕПНЫХ ДРОБЕЙ
179
числа при і = 0,2,4. Соответствующие векторы равны (1,4,1,0), (1,0,0,1) и (1,0,3,0). Сумма первого и третьего — нулевой вектор по модулю 2. Поэтому полагаем Ь = 95 ¦ 2619 ее 3834 (mod 9073) и с = 22 • З2 = 36. Таким образом, 38342 ее 362 (mod 9073). Так как 3834 ее 36 (mod 9073), мы получаем нетривиальный делитель: НОД (3834 + 36, 9073) = 43. Итак, 9073 = 43 • 211.
Пример 3. Разложить на множители 17873.
Решение. Как и в примере 2, мы начинаем с таблицы:
і 0 1 2 3 4 5
аг 133 1 2 4 2 3
Ь; 133 134 401 1738 3877 13369
Ъ\ (mod п) -184 83 -56 107 -64 161
Если положить В = { — 1,2,7,23}, то Б-числа получаются при г = 0,2,4,5; соответствующие векторы сц равны (1,3,0,1), (1,3,1,0), (1,6,0,0) и (0,0,1,1). Сумма 1-го, 2-го и 4-го из этих векторов — нулевой вектор по модулю 2. Однако если вычислить Ь = 133 ¦ 401 • 13369 ее 1288 (mod 17873) и с = 23 • 7 • 23 = 1288, то окажется, что Ь ее с (mod 17873). Поэтому приходится продолжить поиск Б-чисел, которым соответствуют векторы с суммой, равной нулю по модулю 2. Продолжая таблицу, получаем:
і 6 7 8
а{ 12 1
Ьг 17246 12115 11488
Ъ] (mod п) -77 149 -88
Если мы теперь расширим В, включив туда еще простое число 11, т.е. В = {-1,2,7,11,23}, то для г = 0,2,4,5,6,8 получаем Б-числа со следующими векторами q^: (1,3,0,0,1), (1,3,1,0,0), (1,6,0,0,0), (0,0,1,0,1), (1,0,1,1,0), (1,3,0,1,0). Замечаем, что сумма 2-го, 3-го, 5-го и 6-го векторов равна нулю по модулю 2. Это дает Ь = 7272, с = 4928, и мы находим, наконец, нетривиальный делитель: НОД (7272 4- 4928,17873) = 61. Таким образом, 17873 = 61 • 293.
УПРАЖНЕНИЯ
1. Найти представление в виде цепной дроби следующих рациональных чисел: а) 45/89; б) 55/89; в) 1,13.
