Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
сей раз останавливаясь на скачках величины 243.
После прохождения этой процедуры для остальных 6 чисел нашей факторной базы мы получаем таблицу размера 500 X 8 из показателей степеней, в которой каждая строка соответствует значению t от 1021 до 1520. Теперь мы отбрасываем все строки, для которых t — п не превратилось в 1 при повторном делении на степени р в процессе фор-
2
мирования таблицы, т. е. мы берем только строки, для которых t — п есть Б-число. В рассматриваемом примере с п = 1042387 останется следующая таблица (с прочерками на месте нулевых показателей степени).
t
і2 - п
2
3
11
17
19
23
43
47
1021
54
1
3
1027
12342
1
1
2
1
—
-
-
-
1030
18513
-
2
2
1
-
-
-
-
1061
83334
1
1
-
1
1
1
-
1112
194157
-
5
-
1
-
-
1
1129
232254
1
3
1
1
-
1
—
-
1148
275517
-
2
3
-
-
1
-
-
1175
338238
1
2
-
-
1
1
1
-
1217
438702
1
1
1
2
1
-
-
1390
889713
—
2
2
-
1
-
1
-
1520
1268013
—
1
—
1
—
2
—
1
Продолжая так же, как мы делали в примере 9 из § 3, ищем теперь соотношения по модулю 2 между строками этой матрицы, т.е., двигаясь сверху вниз, ищем такие наборы строк, суммы элементов которых в каждом столбце четны. Первый обнаруживаемый набор такого типа — это первые три строки, сумма которых — удвоенная строка 1321 - - — — . Таким образом, мы получаем сравнение
(1021 • 1027 • 1030)2 = (2 • З3 • П2 • 17)2 (mod 1042387).
Однако, хотя нам и повезло быстро найти подмножество строк, линейно зависимых по модулю 2, эта удача неполная: оба возводимые в квадрат числа в последнем сравнении сравнимы с 111078 по модулю 1042387, и мы получаем лишь тривиальную факторизацию. Продвигаясь вниз по таблице, мы находим еще несколько наборов линейно зависимых строк, которые также не дают нетривиальной факторизации. Наконец, когда мы уже почти готовы сдаться и начать все сначала с увеличенным А, мы замечаем, что последняя строка, соответствующая нашему самому последнему значению і, зависит от предшествующих строк. А именно, по модулю 2 она равна 5-й строке. Это дает нам (1112 • 1520)2 = (З3 • 17 • 23 • 47)2 (mod 1042387),
§ 5. МЕТОД КВАДРАТИЧНОГО РЕШЕТА
185
т.е. 6478532 = 4961792 (mod 1042387), и мы получаем нетривиальный делитель: НОД (647853 - 496179,1042387) = 1487.
Используя некоторые правдоподобные предположения, можно показать, что математическое ожидание времени работы метода разложения при помощи квадратичного решета имеет порядок
Метод использует очень большой объем памяти (также порядка exp {C\/log п log logn}). Подробное обсуждение характеристик алгоритма факторизации при помощи квадратичного решета (и некоторых других) можно найти в статье Померанца из списка литературы к этому параграфу.
Решето в числовом поле. До недавнего времени все оценки времени работы лучших универсальных алгоритмов разложения на множители имели вид
Некоторые даже предполагали, что эта функция п является естественной нижней границей для времени работы. Однако в течение последних нескольких лет был разработан новый метод, названный решетом в числовом поле. Эвристическая оценка времени его работы значительно лучше (асимптотически):
Практически он оказался самым быстрым методом для разложения на множители чисел, которые имеют величину, максимально допустимую для современных (1994 г.) методов факторизации, или немного превышают ее, т.е. для чисел, имеющих в десятичной системе счисления немного больше 150 знаков.
Факторизационный алгоритм решета в числовом поле во многом подобен ранее рассмотренным алгоритмам, в которых проводится поиск наборов сравнений, дающих соотношение вида х2 = у2 (mod п). Однако в нем используется «факторная база» в кольце целых чисел некоторого надлежаще выбранного поля алгебраических чисел. Таким образом, наряду с основной техникой квадратичного решета, в этом методе факторизации применяется также теория алгебраических чисел. Видимо, это наиболее сложный из известных факторизационных алгоритмов. Мы дадим только его набросок.
Основные требования алгоритма можно кратко описать следующим образом. Если нужно разложить на множители число п, то нужно
0{е
для любого є > 0.
exp {O((logn)1/3(loglogn)2/3)}.
186
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
выбрать некоторую степень d и выразить п как значение при некотором целом т неприводимого нормированного многочлена степени d:
п = }(т) = гп + ad_1md~1 + ad_2md~2 +----(- axm + а0,
где m и ?fc — целые числа, порядок величины которых — 0(n1/,d). Один из способов найти такой многочлен — это взять в качестве тп целую часть корня степени d из п и затем разложить п по основанию т. Для 125-значных чисел анализ алгоритма показывает, что d должно равняться 5, и потому т и коэффициенты должны быть примерно 25-значными.
Решето числового поля тогда отыскивает (с помощью того же процесса, что и в случае квадратичного решета) максимально возможное число таких пар (а, 6), что как число a + Ьт, так и число
