Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
До начала работы с кривой E по модулю п нужно проверить, что это — действительно эллиптическая кривая по модулю любого р\п, т. е. что кубический многочлен в правой части уравнения не имеет кратных корней по модулю р. Это справедливо тогда и только тогда, когда дискриминант 4а +276 взаимно прост с п. Таким образом, если
3 2
НОД (4а° + 276 ,п) = 1, мы можем действовать. Конечно, если НОД не равен 1 или п, мы получаем искомый делитель п. Если этот НОД равен п, то нам следует выбрать другую эллиптическую кривую.
Далее, предположим, что мы выбрали два натуральных числа В и С. Здесь В — максимальная величина простого делителя того целого числа к, на которое мы будем умножать точку Р. Чем больше
B, тем больше вероятность того, что кР (mod р) = О (mod р) для нашей пары (Е,Р) и некоторого р\п; с другой стороны, чем больше В, тем дольше придется вычислять кP (mod р). Поэтому В нужно выбирать таким образом, чтобы (по нашей оценке) минимизировать время работы. Число С должно служить как бы верхней границей для того простого делителя р\п, с которым мы надеемся в конце концов получить соотношение кP (mod р) = О (mod р). Затем мы выбираем к по формуле (2), т.е. представленным в виде произведения степеней простых чисел, не превосходящих В, каждая из которых не превосходит
C. Тогда, согласно теореме Хассе, если р + 1 + 2^/р < С и порядок кривой E (mod р) не делится ни на какое простое число, большее Р, то к кратно этому порядку и потому кP (mod р) = О (mod р).
Пример 3. Предположим, что мы выбрали В = 20 и хотим разложить на множители 10-значное (в десятичной системе) число п, которое может быть произведением двух 5-значных простых чисел (т. е. п не делится ни на какое простое число, записываемое менее, чем 5 знаками). Тогда выбираем С = 100700 и к = 2 • 3 • 5 • 7 ¦ П4 • 134 • 174 • 193.
Вернемся к описанию алгоритма. Работая по модулю тг, пытаемся вычислять кР следующим образом. Используя метод повторного удвоения, находим 2Р, 2(2Р), 2(4Р),..., 2°2Р, вслед за этим 3(2а2)Р,
224
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
3(3 • 2°2Р),..., Заз2°2Р и т.д., пока, наконец, не получим Пкв^'Р (умножаем, последовательно переходя от самых малых простых делителей / числа к к самым большим). В этих вычислениях при каждом делении по модулю п применяем алгоритм Евклида для нахождения обратного элемента. Если на какой-либо стадии алгоритм Евклида не дает обратного элемента, то либо найден нетривиальный делитель п, либо в качестве НОД п и этого знаменателя получено само п. В последнем случае следует возвратиться к началу и взять другую пару (Е,Р). Если алгоритм Евклида всегда дает обратный элемент — и, таким образом, кР (mod п) вычисляется, — следует возвратиться к началу и взять другую пару (Е,Р). Описание алгоритма завершено.
Пример 4. Используем семейство эллиптических кривых у = Xі + ах - а, а = 1,2,..., каждая из которых содержит точку P = (1,1). Пе^эед использованием а мы должны проверить, что дискриминант 4а +27а взаимно прост с п. Попытаемся разложить п = 5429, полагая В = 3 и С = 92. (В этом примере и в приведенных ниже упражнениях мы иллюстрируем метод, используя небольшие значения п. Конечно, на практике достоинства метода проявляются лишь при несравненно больших п). Здесь наш выбор С объясняется желанием найти простой делитель, который может принимать значения до у/п « 73; для р = 73 верхняя оценка общего числа Fp-точек — это 74 + 2\/73 < 92. Согласно (2) выбираем к = 26 • З4. При каждом значении а мы последовательно умножаем шесть раз точку P на 2 и затем четыре раза на
2 3
3, работая по модулю п на эллиптической кривой у = х + ах - а. Когда а = 1, все вычисления проходят гладко ті тем самым выясняется, что 3426Р (mod р) — конечная точка на E (mod р) для каждого р\п. Следующая попытка — с а = 2. В этом случае при вычислении 3226Р (mod р) мы получаем знаменатель, у которого НОД с п равен 61, т.е. находим собственный делитель п. Таким образом, порядок точки (1,1) на кривой у2 = X3 + 2х - 2 по модулю 61 является делителем 322 (см. упражнение 5 ниже). Итак, вторая попытка оказалась успешной. Кстати, если мы возьмем а = 3, то при вычислении 3426Р найдем другой простой делитель числа, равный 89. (Обычно, но не всегда, этот метод дает наименьший простой делитель.)
Время работы. Центральным вопросом при оценке времени работы является вычисление вероятности того, что при заданном р и заданной границе В (выбранной некоторым оптимальным образом) порядок TV случайной эллиптической кривой по модулю р не делится ни на какое простое число, большее В. Известно, что порядки N эллиптических кривых, находящиеся (по теореме Хассе) в интервале [р + 1 - 2у/р,р + 1 + 2у/р], распределены в нем довольно равномерно (с
§ 4. РАЗЛОЖЕНИЕ HA МНОЖИТЕЛИ
225
тем исключением, что вблизи концов интервала плотность значений JV падает). Значит, эта вероятность приближенно равна вероятности того, что случайно выбранное целое число величины примерно р не делится ни на какое простое число, большее В. Мы уже видели при выводе эвристической временной оценки в § V. 3, что эта вероятность есть примерно и и, где и = (logp)/(log В). Это приводит к оценке
