§ 3. Применение эллиптических кривых в задаче факторизации чисел
Опишем алгоритм разложения целых чисел на простые множители, основанный на арифметических свойствах эллиптических кривых над конечными полями. Алгоритм разработан Ленстрой.
Предварительно рассмотрим вопрос вычисления кратной точки на кривой и докажем одно вспомогательное утверждение.
Кратные точки. Рассмотрим алгоритм вычисления точки 𝑘𝑃. Представим число 𝑘 в двоичном виде:
𝑘 =
+
⋅
2 +
⋅
+ … +
⋅
,
0,1.
Далее, положим
=
𝑃,
=
2
= 2𝑃,
…………………
=
=
,
откуда
Таким
образом, мы можем вычислить 𝑘𝑃
самое большее за
шагов, каждый из которых представляет
собой сложение точек на кривой.
Пример 15. Чтобы найти 100𝑃, представляем 100 в виде
100
=
Далее,
.
Теперь
100𝑃
=
Мы нашли точку 100𝑃, произведя 6 удвоений и 2 сложения точек на кривой.
Замечания.
1) приведенная
оценка времени работы не является
наилучшей, особенно для конечных полей
характеристики р
= 2. Нам, однако, достаточно этой оценки;
2) если известно число N
точек на эллиптической кривой Е
и если k
> N,
то в силу равенства NP
= 𝒪
мы можем заменить k
его наименьшим
неотрицательным вычетом по модулю N
(kmodN)
(напомним, что
).
Рене Шуф (R.
Schoof)
предложил алгоритм, вычисляющий N
за O(
)
двоичных операций.
Докажем теперь свойство точек эллиптической кривой, необходимое для алгоритма Ленстры.
Теорема 10. Пусть эллиптическая кривая задана уравнением
(26)
коэффициенты 𝑎 и 𝑏 которого – целые числа и пусть 𝑃 = (𝑥, 𝑦) – точка на этой кривой с рациональными координатами. Тогда 𝑥 и 𝑦 имеют вид
𝑥 =
,
𝑦
=
,
где 𝑚, 𝑛, 𝑒 – целые числа, 𝑒 > 0 и (𝑚, 𝑒) = (𝑛, 𝑒) = 1.
Доказательство. Запишем рациональные числа 𝑥 и 𝑦 в виде несократимых дробей
𝑥 =
,
𝑦
=
,
где 𝑀 > 0 и 𝑁 > 0. Подставляя 𝑥 и 𝑦 в уравнение кривой (26), получаем
или
(27)
Так
как
является делителем всех слагаемых в
правой части этого равенства, то
.
Но (𝑛,
𝑁)
= 1; следовательно,
Покажем
теперь, что
.
Прежде всего из равенства (27) непосредственно
следует, что
,
а так как (𝑚,
𝑀)
= 1, то
.
Используя этот факт и равенство (27),
находим что
т. е. что
.
И, наконец, ещё раз используя
равенство (27), получаем, что
,
откуда
.
Итак,
мы показали, что
и
,
поэтому
.
Кроме того, в процессе доказательства
мы установили, что
.
Таким образом, если положить 𝑒
=
,
то
.
Следовательно,
𝑥 = , 𝑦 = ,
что и требовалось доказать.
Теперь, основываясь на алгоритме вычисления кратной точки и на теореме, опишем факторизационный алгоритм Ленстры.
Прототипом
алгоритма Ленстры является алгоритм
Полларда. Алгоритм Полларда основан на
том, что нетривиальные элементы в ℤ/𝑝ℤ
образуют группу (ℤ/𝑝ℤ)∗
порядка 𝑝⎯1.
Поэтому, если 𝑝⎯1│𝑘
, то в этой группе выполняется равенство
=
1.
Идея
Ленстры состоит в том, чтобы заменить
группу (ℤ/𝑝ℤ)∗
группой точек эллиптической кривой
𝐸(
),
а число 𝑎
– точкой 𝑃∈𝐸(
).
Как и в алгоритме Полларда, мы выбираем
число 𝑘,
являющееся произведением небольших
простых чисел в небольших степенях.
Если окажется, что число элементов в
𝐸(
)
делит 𝑘,
мы будем иметь в этой группе равенство
𝑘𝑃
= 𝒪.
И точно так
же, как в алгоритме Полларда, это равенство
в общем случае позволит нам найти
нетривиальный делитель числа 𝑛.
Опишем преимущество алгоритма Ленстры в сравнении с алгоритмом Полларда.
Если
мы ограничимся только одной кривой 𝐸
с целыми коэффициентами и будем
рассматривать её редукции по модулю
различных простых чисел, то никакого
преимущества по сравнению с алгоритмом
Полларда мы не получим. В самом деле,
для фиксированной 𝐸
мы достигнем успеха, если найдётся такой
простой делитель 𝑝,
𝑁
,
который является произведением небольших
простых чисел. Эта ситуация вполне
аналогична ситуации в алгоритме Полларда.
Но если в алгоритме Полларда не удаётся
быстро достичь успеха, его работа должна
быть остановлена. В алгоритме Ленстры
существуют дополнительные, очень широкие
возможности продолжать работу: имеется
свобода в выборе новой эллиптической
кривой. Так как числа 𝑁
при фиксированном 𝑝
изменяются в достаточно широких пределах
для различных кривых 𝐸,
то в принципе можно надеяться во всех
случаях достигнуть успеха.
Формально алгоритм Ленстры заключается в следующем.
Шаг
1. Выбираем
целые числа 𝑏,
,
,
лежащие между 1
и
𝑛.
Шаг 2. Полагаем
𝑐 =
–
–
(mod
𝑛)
(28)
и рассматриваем кубическую кривую
𝐸 : = + 𝑏𝑥 + 𝑐, 𝑏, 𝑐 ∈ ℤ (29)
и точку 𝑃 = ( , ) на ней.
Шаг 3. Вычисляем наибольший общий делитель
,
(30)
т.
е. проверяем, являются ли редукции кривой
𝐸
эллиптическими
(
–
это взятый с обратным знаком дискриминант
многочлена
+ 𝑏𝑥
+ 𝑐).
Если
= 𝑛,
возвращаемся к началу и выбираем новое
𝑏.
Если 1 <
<
𝑛,
получим нетривиальный делитель числа
𝑛.
Если же
= 1, переходим к следующему шагу.
Шаг 4. Выбираем число 𝑘, являющееся произведением небольших простых чисел в небольших степенях. Например,
𝑘 =
НОК
,
где М – некоторое натуральное число.
Шаг 5. Вычисляем
𝑘𝑃
=
.
Шаг
6. Вычисляем
𝐷
=
.
Если 1 < 𝐷
< 𝑛,
то 𝐷
является нетривиальным делителем числа
𝑛.
Если 𝐷
= 1, либо возвращаемся к шагу 4 и
увеличиваем
𝑘,
либо возвращаемся к шагу 1 и выбираем
новую кривую. Если 𝐷
= 1, возвращаемся к шагу
4 и уменьшаем
𝑘.
В настоящее время существуют алгоритмы проверки натуральных чисел на простоту, использующие эллиптические кривые над конечными полями. Эта область теории эллиптических кривых бурно развивается и далека еще от завершения.
* * *
Теорию эллиптических кривых с комплексным умножением можно изучить по руководству [3]. Современное, подробное изложение теории алгебраических кривых содержится в [6]. С алгоритмами проверки на простоту можно ознакомиться по книге [7]. Для углубленного изучения теоретико-числовых алгоритмов полезной является книга [1].