Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 91 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 3. Эллиптические кривые 92
Пример 1. Пусть требуется разложить число n = 455 839. Выберем
эллиптическую кривую
y
2
= x
3
+ 5x − 5,
точку P = (1, 1) на ней и постараемся вычислить 10! P .
1. Найдем сначала 2P . Тангенс угла наклона касательной λ в т.P
равен λ = (3 · 2 + 5)/(2y) = 4 и координаты P
2
= 2P = (x
2
, y
2
) =
(14, −53) (modn).
2. Вычислим далее, P
3
= 3(2P) = 3P
2
. Прямой формулы для
вычисления точки 3P
2
нет, поэтому придется вычислить сначала 2P
2
, затем
получить 3P
2
, суммируя точки 2P
2
и P
2
. Получим 2P
2
= (259 851, 116 255),
3P
2
= (195 045, 123 227).
3. Продолжая эту процедуру вычислим 4!P , потом 5!P и т.д.
При вычислении 8!P знаменатель λ станет равным 599 и вычисление
Н.О.Д.(n, 599) даст значение d = 599. Отсюда 599 является делителем n, и
деля n на 599 найдем второй делитель n: 455839 = 599 · 761.
Причина, по которой процесс сошелся при вычислении 8!P , состоит в
том, что кривая y
2
= x
3
+ 5x − 5 ( mod 599) содержит 640 = 27 · 5 точек.
Вторя кривая y
2
= x
3
+5x−5 ( mod 761) содержит 640 = 27·5 точек. Число
8! делится на 640, но не делится на 777. Поэтому первым появился делитель
p = 599.
Анализ метода Ленстры
Проведем теперь анализ метода Ленстры и оценим условия, при которых он
будет успешно завершен. До сих пор все вычисления проводились по модулю
числа n, однако, если координаты полученных точек вычислять по модулю p,
являющегося делителем n, тогда условием успешного завершения алгоритма
будет, очевидно, условие
kP = ∞, где k =
Y
p
a
i
i
≤B
1
p
a
i
i
, (3.66)
Глава 3. Эллиптические кривые                                            92

      Пример 1. Пусть требуется разложить число n = 455 839. Выберем
эллиптическую кривую

              y 2 = x3 + 5x − 5,

точку P = (1, 1) на ней и постараемся вычислить 10! P .

      1. Найдем сначала 2P . Тангенс угла наклона касательной λ в т.P
равен λ = (3 · 2 + 5)/(2y) = 4 и координаты P2 = 2P = (x2 , y2 ) =
(14, −53) (modn).
      2. Вычислим далее, P3 = 3(2P ) = 3P2 . Прямой формулы для
вычисления точки 3P2 нет, поэтому придется вычислить сначала 2P2 , затем
получить 3P2 , суммируя точки 2P2 и P2 . Получим 2P2 = (259 851, 116 255),
3P2 = (195 045, 123 227).
      3. Продолжая эту процедуру вычислим 4!P , потом 5!P и т.д.
При вычислении 8!P знаменатель λ станет равным 599 и вычисление
Н.О.Д.(n, 599) даст значение d = 599. Отсюда 599 является делителем n, и
деля n на 599 найдем второй делитель n: 455839 = 599 · 761.
      Причина, по которой процесс сошелся при вычислении 8!P , состоит в
том, что кривая y 2 = x3 + 5x − 5 ( mod 599) содержит 640 = 27 · 5 точек.
Вторя кривая y 2 = x3 + 5x − 5 ( mod 761) содержит 640 = 27 · 5 точек. Число
8! делится на 640, но не делится на 777. Поэтому первым появился делитель
p = 599.

           Анализ метода Ленстры

Проведем теперь анализ метода Ленстры и оценим условия, при которых он
будет успешно завершен. До сих пор все вычисления проводились по модулю
числа n, однако, если координаты полученных точек вычислять по модулю p,
являющегося делителем n, тогда условием успешного завершения алгоритма
будет, очевидно, условие
                                       Y
                    kP = ∞, где k =              pai i ,              (3.66)
                                       a
                                      pi i ≤B1

Страницы