Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Как же практически выбирать факторную базу В ж Один из методов: в качестве В взять первые h простых чисел (или первые Zi-I простых ж р] = —1); числа Ь{ выбирать случайно, пока не найдется несколько таких, что их квадраты — 5-числа. Другой метод: выбрать сначала несколько чисел для которых Ъ± (mod п) (наименьшие абсолютные вычеты) малы по абсолютной величине (например, выбрать hi близкими к \fk~n для малых к или так, как будет описано в § 4). Затем выбираем в качестве В небольшую совокупность малых простых чисел (включая в него также рх = -1), чтобы несколько Ь\ (mod п) можно было выразить через числа из В.
Пример 6. В ситуации примеров 4-5 мы выбирали 67 и 68, так как они близки к у/4633. Обнаружив, что 67 = -144 ( mod 4633), 682 = -9 (mod 4633), мы положили В = {-1,2,3}. Как мы видели, числам 67 и 68 соответствуют векторы (1, 0, 0), и их сумма — нулевой вектор. Поэтому b = 67-68 = -77 (mod 4633) и с = 272 373 (степенью -1 в с мы можем пренебречь), т. е. с = 36. Так как —77 ф ±36 (mod 4633), то мы находим делитель, вычисляя НОД ( — 77 + 36,4633) = 41.
Сколько нужно иметь Ь{, чтобы можно было найти сумму ?,-, равную нулевому вектору? Другими словами, какой объем должна иметь совокупность векторов из F2 ,_чтобы она содержала в себе подмножество векторов с нулевой суммой, т.е. чтобы она была линейно зависимой над полем F2. Согласно основам линейной алгебры (справедливым над полем F2 так же, как и над полем вещественных чисел) любые h 4- 1 векторов линейно зависимы. Поэтому в худшем случае нам нужно образовать h + 1 различных і?-чисел, чтобы найти первый пример сравнения вида J-Jі ^ = (YIj р]3) (modn). (Пример 6 показывает, что линейно зависимые векторы могут получиться и раньше; в этом примере h = 3, а мы остановились, найдя два 5-числа). Если h велико, то, возможно, поверхностный просмотр не позволит выделить подмножество векторов с нулевой суммой. В этом случае нам следует записать векторы в виде строк матрицы и с помощью методов линейной алгебры (обнуляя строки) найти множество линейно зависимых строк.
Пример 7. Пусть п = 4633. Найти такую наименьшую факторную базу В, чтобы квадраты 68, 69 и 96 были Б-числами, и затем разложить 4633.
2 2
Решение. Как мы уже убедились, 68 (mod п) и 69 (mod п)
2
являются произведениями чисел —1,2 и 3; так как 96 = —50 (mod п),
§ 3. ФАКТОРИЗАЦИЯ ФЕРМА И ФАКТОРНЫЕ БАЗЫ
165
наименьшие абсолютные вычеты всех трех квадратов можно выразить через элементы факторной базы В = { — 1, 2, 3,5}. Мы уже нашли векторы E1 = (1,0,0,0) и е2 = (0,1,0,0), отвечающие, соответственно, 68 и 69. Так как 962 = -50 (mod 4633), то є3 = (1,1,0,0). Эти три вектора имеют нулевую сумму, поэтому возьмем 6 = 68-69-96 = 1031 (mod 4633) и с = 24-3-5. Находим: НОД (1031 + 240,4633) = 41.
Примеры 6 и 7 демонстрируют систематический способ поиска нескольких Ь{ таких, что наименьшие абсолютные вычеты bj (mod п) оказываются произведениями малых простых чисел. Вероятность то-го, что 6j (mod п) есть произведение малых простых, увеличивается, если этот вычет мал по абсолютному значению. Таким образом, мы можем последовательно пробовать целые числа bj, близкие к у/кп для малых значений к. Например, мы можем выбрать , + 1 для
к = 1,2,...
Пример 8. Разложим на множители п = 1829, выбирая в качестве bj все такие числа [у/ЇШк], [V1829A] + 1, к = 1,2,..., что bj (mod п) есть произведение простых чисел, меньших 20. Представляем такие числа в виде bj (mod п) = YIj P°j" и составляем таблицу из ctjj. Рассмотрев к = 1,2,3,4, получаем таблицу, в которой первым элементом j-то столбца является pj, а элемент этого столбца в строке, соответствующей значению bj, — это показатель, с которым Pj входит в разложение Ьг (mod п).
Ьг -1 2 3 5 7 И 13
42 1 - - 1 - - 1
43 -2-і - - -61 - - 2 - 1 - -74 1 - - - - 1 -
85 1 - - - 1 - 1
86 - 4 - 1 - - -
Ищем теперь множества строк, у которых суммы элементов в каждом столбце четны. Сразу видно, что сумма 2-й и 6-й строк четная:
-6-2---. Это дает сравнение (b2b6)2 = (26/'252/'2)2 (mod п), т.е.
(43-86)2 = 402 (mod 1829). Но так как 43-86 = 40 (mod 1829), мы нашли лишь тривиальное соотношение. Поэтому приходится искать другие подмножества строк, суммы которых содержат лишь четные элементы. Мы замечаем, что таковы строки 1, 2, 3 и 5; их сумма 2 222 2 — 2;
2 2
это дает сравнение (42 • 43 • 61 • 85) = (2 • 3 • 5 • 7 • 13) (mod п), т. е.
2 2
1459 = 901 (mod 1829). Мы получаем отсюда, что делителем 1829 является НОД (1459 + 901,1829) = 59.
166
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
Алгоритм факторных баз. Опишем теперь систематический метод факторизации очень большого п при помощи случайного выбора чисел 6j. Выбираем целое число у «промежуточной» величины, например, если п — 50-значное десятичное число, то выбираем в качестве у число с 5 или 6 десятичными знаками. Пусть В состоит из -1 и всех простых чисел, не превосходящих у. Выбираем случайным образом много Ьг и пытаемся разложить Ьг (mod п) (наименьшие абсолютные вычеты) в произведение чисел из В. Получив большое количество 5-чисел &j (mod ті) (достаточно найти ж (у) + 2 таких чисел, где тт(у) — число простых, не превосходящих у), вычисляем соответствующие векторы в F2 (где h = тт(у) + 1) и с помощью обнуления строк находим такое подмножество Ьи что сумма соответствующих векторов Ei дает нулевой вектор. Затем образуем ь = bi (mod п) и с = YIj р]' (mod п) так, как это было описа-
