Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
4. Предполагая, что р — такое нечетное простое число, что п — квадратичный вычет по модулю р (случай р = 2 разберем далее от-дельно), решаем уравнение t = п (mod р ) для ? = 1,2,... методом упражнения 20 к § П. 2. Берем значения ? в порядке возрастания, пока не окажется, что уравнение не имеет решений t, сравнимых по модулю р^ с каким-либо из чисел в области [-\/тї] + 1 ^ t ^ [-^/тг] + А. Обозначим через ? наибольшее из таких чисел, для которых в указанной области
2 в
найдется число t со свойством t = п (mod р ). Пусть i1 и i2 — два решения i2 = п (mod р13) и i2 = -i1 (mod p0) (мы не требуем, чтобы i1 и i2 принадлежали отрезку [[у/п\ 4 1, + А]).
5. При том же самом значении р просматриваем список значений t - п, полученный в п. 2. В столбце, соответствующем р, ставим 1 против всех значений t — п, для которых t отличается от t\ на некоторое кратное р, после этого заменяем 1 на 2 для всех таких значений і — п, что t отличается от i1 на кратное р , затем заменяем 2 на 3 у
2 3
всех значений t — п, для которых t отличается от i1 на кратное р , и так далее до р^. Затем делаем то же самое- с i2 вместо i1. Наибольшим числом, которое появляется в этом стожэце, будет ?.
6. Когда производим действия в пл5, каждый раз, когда ставим
1 или заменяем 1 на 2, 2 на 3 и т.д., делим соответствующее число
,2
t — п на р и сохраняем полученный результат.
7. В столбце под р = 2 при п ф 1 (mod 8) просто ставим 1 против
2 2
t —пс нечетным t и делим соответствующее і - її на 2. При п =
2 Q
1 (mod 8) решаем уравнение / = п (mod 2 ) и продолжаем в точности так же, как в случае нечетного р (за исключением того, что при /3^3 уравнение будет иметь 4 различных решения t1,t2,t3,t4).
8. Когда указанные действия будут проведены для всех простых чисел, не превосходящих Р, отбросим все і — п, кроме тех, которые обратились в 1 после деления на все степени р, не превосходящих Р. Тогда получится таблица того же вида, что в примере 9 из § 3, в которой столбец, помеченный bi, будет содержать все такие значения t из интервала [[\/п\ + 1, [у/п\ + А], что і2 — п есть Б-число, а остальные столбцы будут соответствовать тем значениям р ^ Р, для которых п — квадратичный вычет.
9. Оставшаяся часть процедуры в точности совпадает с процедурой из § 3.
§ 5. МЕТОД КВАДРАТИЧНОГО РЕШЕТА
183
Пример. Давайте попытаемся разложить на множители п = 1042387, выбрав границы P = 50 и А = 500. Здесь [у/п[ = 1020. Наша факторная база состоит из 8 простых чисел {2,3,11,17,19,23,43,47}, для которых 1042387 — квадратичный вычет. Так как п ф 1 (mod 8), то в столбце, соответствующем р = 2, стоят лишь 0 и 1, причем 1 проставляется во всех случаях, когда Z нечетно, 1021 ^ Z ^ 1520.
Опишем подробно, как образуется столбец для р = 3. Мы хо-
2 в — 1
тим найти решение Z1 = Zlj0 + іідЗ + 23 + • • • + h,?-i^ сравне-
2 в
ния Z = 1042387 (mod 3 ), где Z1^ є {0,1,2} (за другое решение Z2
МОЖНО ПРИНЯТЬ I2 = З13 — Z1). MbI МОЖеМ, ОЧеВИДНО, ВЗЯТЬ Z1 0 = 1.
(Для каждого из наших 8 простых чисел первый шаг — решение сравнения t = 1042387 (mod р) — можно сделать быстро методом проб и ошибок; если бы мы работали с большими простыми числами, мы могли бы использовать процедуру, описанную в конце §11.2.) За-тем мы работаем по модулю 9: (1 + 3Ziд) = 1042387 = 7 (mod 9), откуда 6Z11 = 6 (mod 9), т.е. 2Z1^1 = 2 (mod 3) и д = 1. Далее, по модулю 27: (1 + 3 + 9Zli2)2 = 1042387 = 25 (mod 27), т.е. 16 + 18^i 2 = 25 (mod 27) и 2ti2 = 1 (mod 3), так что f1]2 = 2. Затем по модулю 81: (1 + 3 + 18 + 27^,3)2 = 1042387 = 79 (mod 81), откуда еле-дует, что Z1 з = 0. Продолжая действовать так же до 3 , мы находим решение (в обозначениях § I. 1 для чисел, записываемых в троичной системе): Z1 = (21021I)3 (mod З7) и Z2 = (2012012)3 (mod З7). Однако в интервале между 1021 и 1520 нет числа Z, сравнимого с Z1 или Z2 по модулю 3 . Таким образом, мы имеем ? = 6, и можно взять Z1 = (21021I)3 = 589 = 1318 (mod З6) и Z2 = З6 - Z1 = 140 = 1112 (mod З5) (заметим, что в отрезке [1021,1520] нет числа Z, сравнимого с Z2 по модулю З6).
Построим теперь наше «решето» для р = 3. Начиная с 1318, делаем «прыжки» на 3 вниз, пока не достигнем 1021, и такие же «прыжки» вверх, пока не достигнем 1519; каждый раз ставим 1 в столбец, если Z2 — п делится на 3, и записываем результат деления (на самом деле
2
для нечетного Z число, которое мы делим на 3, равно (Z — п)/2, так 2
как мы уже делили Z - п пополам, когда формировали столбец из 0 и 1 для р = 2). Затем мы делаем то же самое, «прыгая» на 9, изменяя каждый раз 1 на 2 в столбце под 3, деля еще раз на 3 то, что осталось от соответствующего Z2 —п, и записывая результат. Проделываем аналогичную процедуру со скачками на 27, 81, 243, 729 (для 729 скачка не существует — мы только изменяем 5 на 6 в графе, соответствующей 1318, и делим еще раз на 3 то, что осталось от 1318 - 1042387). Наконец, мы проделываем те же шаги с Z2 = 1112 вместо Z1 = 1318, на
184
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
