Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
= X3 A- OX1 + 6+- ргх(3х2 + а) = у\ + ргх{Ъх\ Ar a) (mod рг+1).
Так как х2 = X1 (mod р) и у2 = Jz1 (mod р), то P1 (mod р) = P2 (mod р), т.е. Pi (mod р) +- P2 (mod р) = 2P1 (mod р). Очевидно, что 2Pi (mod р) = О (mod р) тогда и только тогда, когда уг = у2 =
2 2
О (mod р). Если это сравнение выполнено, то y2 — yi = (у2 — Ух )(у2 + 2/i)
г+1 / г-Н
должно делиться на р (т. е. должен делиться на р числитель этого рационального числа). Поэтому из сравнения (1) следовало бы,
2 3
что 3xi +- а = 0 (mod р). Но это невозможно, поскольку х + ах + Ь не имеет кратных корней по модулю р, т.е. Xi не может быть общим корнем этого многочлена и его производной. Значит, Pi (mod р) A-P2 (mod р) ф О (mod р), как и утверждалось.
Обратно, пусть Pi (mod р) + P2 (mod р) ф О (mod р) для каждого простого делителя р числа п. Покажем, что знаменатели координат P1 +P2 взаимно просты с п, т. е. что знаменатели не делятся ни на какой простой делитель р числа п. Фиксируем некоторое р\п. Формулы (4), (5) из § 1 показывают, что если х2 ф Xi (mod р), то делящихся на р знаменателей нет. Поэтому предположим, что х2 = хг (mod р). Тогда у2 = ±?/1 (mod р); но так как P1 (mod р) A- P2 (mod р) ф О (mod р), то у2 = г/1 ф 0 (mod р). При P2 = Pi формула (5) из § 1 вместе с условием 2/i^0 (mod р) показывает, что знаменатели координат точки Pi + P2 = 2Pi взаимно просты с р. Наконец, если P2 ф P1, мы вновь пишем х2 = Xi + j)Tx с х, не делящимся на р, и, используя сравнение (1), получаем (у2 - Уі)/(х2 — X1) = Зхі -f a (mod р). Так как р не делит t/1 + 2/2 = 22/1 (mod р), отсюда следует, что знаменатель
2 _ 2 ~
числа (yi + Vy\)[x\-Xl) = x2-j1 не делится на р, и в силу формулы (4) из § 1 знаменатели координат точки Pi + P2 не делятся на р. Теорема доказана.
Метод Ленстры. Пусть дано составное целое нечетное число п и нам нужно найти его нетривиальный делитель d\n, 1 < d < п.
2 3
Берем сначала какую-либо эллиптическую кривую Е: у = х А- ах А~Ь с целыми а, Ь и точку P = (х,у) на ней. Пару (Е,Р) можно выбирать случайным образом или использовать любой детерминистический метод, который порождает много таких пар (как в примере 4 ниже). Мы
222
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
попытаемся с помощью E я P разложить п способом, описанным ниже; если попытка окажется неудачной, то возьмем другую пару (Е,Р) и будем продолжать до тех пор, пока не найдем делитель d\n. Если вероятность неудачи равна р < 1, то вероятность того, что все h последовательно выбранных пар (Е,Р) окажутся неудачными, равна ph, т.е. очень мала для больших h. Таким образом, с высокой вероятностью мы разложим п за приемлемое число шагов.
Имея пару (Е,Р), мы выбираем целое число к, которое делится на степени малых простых чисел (т.е. не больших некоторого В), не превосходящие С. Таким образом, мы полагаем
где ai = [(log С)/(log Z)] есть такой наибольший возможный показатель, что I1^C Далее мы пытаемся вычислить кР, выполняя все действия по модулю п. Результаты этих вычислений не представляют для нас интереса до тех пор, пока при попытке найти число, обратное к X2 — Xi в формуле (4) из § 1 или к Iyx в (5), мы не столкнемся с числом, которое не взаимно просто с п. Согласно предложению VI. 4. 1 это произойдет, когда появится такая точка кхР (частичная сумма в процессе вычисления кР), что кх(P (mod р)) = О (mod р) для некоторого простого делителя р\п, иными словами, порядок P (mod р) в группе E (mod р) является делителем кх. Когда мы, применяя алгоритм Евклида, пытаемся обратить знаменатель, Делящийся на р, мы вместо этого находим НОД числа п и этого знаменателя. Этот НОД и будет искомым собственным делителем п, если он отличен ОТ Tl, т. е. если знаменатель не делится на само п. Однако такая делимость означала бы, по предложению VI.4. 1, что кгР (mod р) = О (mod р) для всех простых делителей р числа п, а это очень маловероятно, если п имеет не менее двух очень больших простых делителей. Таким образом, почти с полной гарантией при попытке вычисления кхР по модулю п для к\, которое делится на порядок точки P (mod р) при некотором р\п, мы получим собственный делитель числа п.
Отметим сходство с (р — 1)-методом Полларда. Вместо группы (Z/pZ)* мы используем группу E (mod р). Однако на сей раз, если наш выбор E неудачен, т. е. для каждого р\п порядок группы E (mod р) делится на большое простое число (и, следовательно, кP (mod р), скорее всего, не совпадает с О (mod р) для к, определенного формулой (2)), то нам нужно просто отбросить ее и выбрать другую эллиптическую кривую E вместе с точкой P Є Е. В методе Полларда такой возможности не было.
к=ці
1^B
§ 4. РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ
223
Алгоритм. Пусть п — нечетное составное натуральное число. Опишем теперь вероятностный метод Ленстры разложения п на множители.
Пусть у нас есть метод порождения пар (Е,Р), состоящих из эл-
2 3
липтической кривой у = X + ах + 6, a, 6 Є Z, и точки P = (х, у) Є Е. Если дана такая пара, то мы проводим описанную ниже последовательность действий. Если посредством этой процедуры не удается получить нетривиальный делитель п, то мы образуем новую пару (E, P) и повторяем процесс.
