Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
162
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
тогда мы вычислим НОД (655 + 68,141467) = 241. Мы получаем тем самым, что 141467 = 241 • 587. Обобщенная факторизация Ферма при к = 3 дала результат потому, что в разложении п = ab множитель Ъ близок к За. При к = 3 нам пришлось пробовать только четыре значения t, тогда как при простой факторизации Ферма (т.е. с к = 1) пришлось бы испробовать 38 значений t.
Факторные базы. Еще одно обобщение идеи, лежащей в основе факторизации Ферма, приводит к значительно более эффективному методу факторизации. А именно, если нам удается получить сравнение вида t2 ее s2 (mod п) с t ф ±s (mod п), то можно сразу найти множитель числа п, вычисляя НОД (t + s, п) (или НОД (t - s, п)). Дей-
2 2
ствителыю, п делит t — s = (t + s)(t - s), но не делит ни t + S, ни t - S] таким образом, НОД (t + s,n) должен быть собственным делителем а числа п, и тогда Ь = п/а делит НОД (t — s,n).
Пример 3. Предположим, что мы хотим разложить на множители 4633 и замечаем, что 118 ее 25 ее 5 (mod 4633). Тогда мы находим, что НОД (118 + 5,4633) = 41, а НОД (118 - 5,4633) = 113, и 4633 = 41 • 113.
Скептик, скорее всего, усомнится в том, что в примере 3 можно было угадать число 118, наименьший положительный вычет квадрата которого является полным квадратом. Возможно ли при случайном выборе разных b быстро получить такое значение, что наименьший положительный вычет b по модулю п есть полный квадрат? Это край-
не маловероятно, если п велико. Поэтому возникает необходимость обобщить этот подход таким образом, чтобы он допускал значительно большую свободу при выборе тех Ь, для которых мы рассматриваем b (mod п). Идея заключается в выборе нескольких &г-, обладающих тем свойством, что b\ (mod п) есть произведение степеней малых простых чисел, а произведение некоторого подмножества дает число, сравнимое по модулю п с полным квадратом. Перейдем теперь к деталям.
Под «наименьшим абсолютным вычетом» числа а по модулю п мы понимаем целое число в интервале от —п/2 до п/2, сравнимое с а. Мы будем обозначать его a (mod п).
Определение. Факторной базой называется множество B = {р\,Р2, ¦ ¦ ¦,Ph}, состоящее из различных простых чисел, кроме числа Pi, которое может равняться —1. Мы скажем, что квадрат числа Ь есть В-число (при заданном п), если наименьший абсолютный вычет Ь (mod п) можно записать как произведение чисел из В.
Пример 4. Пусть п = 4633 и В = {-1,2,3}. Тогда квадраты трех целых чисел — 67, 68, 69 являются Б-числами. Действительно,
672 ее -144 (mod 4633), 682 ее -9 (mod 4633), 692 ее 128 (mod 4633).
§ 3. ФАКТОРИЗАЦИЯ ФЕРМА И ФАКТОРНЫЕ БАЗЫ
163
Пусть F21 обозначает векторное пространство над полем из двух элементов, которое состоит из наборов нулей и единиц, по h в каждом наборе. Если дано п и факторная база В, состоящая из h чисел, то каждому Б-числу можно сопоставить некоторый вектор є є F2. А именно, запишем Ь2 (mod п) в виде Uj=і P°j' и положим j-ю компоненту Ej раВНОЙ Qj (mod 2), Т.е. Ej = О, ЄСЛИ Qj ЧеТНО, И Ej = 1, ЄСЛИ Qj
нечетно.
Пример 5. В ситуации примера 4 вектор, соответствующий 67 — это (1,0,0), числу 68 соответствует также (1,0,0), а числу 69 — вектор (0,1,0).
Предположим, что у нас есть такое множество B-чисел bt (mod n), что сумма соответствующих векторов ? = (ец ,..., Eik) есть нулевой вектор в F2. Тогда произведение наименьших абсолютных вычетов Ь\ равно произведению четных степеней всех Pj, входящих в В, т.е. если для каждого г обозначим через аг наименьший абсолютный вычет Ь\ (mod п) и положим аг = Uj=I Pj'' і то получим
П«< = 1Т>Р";
показатель каждого Pj в правой части — четное число. Тогда правая часть равенства есть квадрат числа YIj р]'> где 7j = \ J2i aij- Таким образом, наименьшие положительные вычеты b = YIi^i (mod п) и с = YIj р]3 (mod п), полученные совершенно различными путями (одно — как произведение чисел bt, другое — как произведение чисел Pj), имеют квадраты, сравнимые по модулю п.
Если оказывается, что Ь = ±с (mod т), то нам не повезло, и мы должны начать снова, с другой совокупностью і?-чисел, у которых соответствующие им векторы дают в сумме нуль. Так произойдет, например, если мы по недосмотру выберем все bi < n/2; все векторы будут тогда нулевыми, и мы придем в итоге к тривиальному сравнению.
Однако при составном п и более случайном выборе следует ожидать, что Ь и с будут сравнимыми (с точностью до ±1) по модулю п не более чем в 50% случаев. Дело в том, что квадрат по модулю п имеет 2Г ^ 4 квадратных корней, если п имеет г ^ 2 различных простых множителей (см. упражнение 7 к § I. 3); значит, случайный квадратный корень из Ь2 лишь с вероятностью 2/2r ^ \ совпадает
2 2
с Ь или — Ь. А если у нас есть такие бис, что Ь = с (mod п), но Ь ф ±с (mod п), мы сразу можем найти нетривиальный множитель НОД (Ь + с,п). Таким образом, если мы А; раз повторяем описанную
164
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
процедуру нахождения b ж с для получения пары, дающей нетривиальный делитель п, то вероятность неудачи в результате всех этих к попыток не превосходит 1/2к.
