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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 85
Пусть P = (x, y) ∈ E , тогда обратной к точкеP является точка −P =
(x, −y). Сумма P + (−P ) = ∞. Сумма точек P = (x
1
, y
1
) и Q = (x
2
, y
2
), где
P 6= −Q, вычисляется по формулам:
x
3
= λ
2
− x
1
− x
2
y
3
= λ(x
1
− x
3
) − y
1
λ =
(
y
2
−y
1
x
2
−x
1
, если P 6= Q,
3x
2
1
+a
2y
1
если P = Q
(3.59)
Группа точек эллиптической кривой над полем F
q
обозначается
символом E(F
q
), а ее мощность (количество элементов) символом #E(F
q
).
Известно, что E(F
q
)
∼
=
C
n
1
⊕ C
n
1
, где C
n
- циклическая группа порядка n,
n
2
делит n
1
, и n
2
делит q − 1.
Пример. Пусть E(F
q
) - группа точек кривой y
2
= x
3
+x+1 над полем
F
23
. Эта группа является циклической с генератором P (0, 1). Рассмотрим все
кратные kP точки P :
P (0, 1) 2P = (6, −4) 3P = (3, −10) 4P = (−10, −7)
5P = (−5, 3) 6P = (7, 11) 7P = (11, 3) 8P = (5, −4)
9P = (−4, −5) 10P = (12, 14) 11P = (1, −7) 12P = (−6, −3)
13P = (9, −7) 14P = (4, 10) 15P = (9, 7) 16P = (−6, 3)
17P = (1, 7) 18P = (12, −4) 19P = (−4, 5) 20P = (5, 4)
21P = (11, −3) 22P = (7, −11) 23P = (−5, −3) 24P = (10, 7)
25P = (3, 10) 26P = (6, 4) 27P = (0, −1) 28P = (∞)
Таким образом, данная кривая содержит 28 точек. Порядок точки A
— это наименьшее натуральное число k такое, что kA = ∞. Порядок любой
точки является делителем порядка числа точек, поэтому, порядок любой
точки на данной кривой принадлежит множеству {1, 2, 4, 7, 14, 28}.
Пример. Найти сумму точек 3P = (3, −10) и 7P = (11, 3).
Решение. Вычислим λ = (y
2
− y
1
)/(x
2
− x
1
): y
2
− y
1
= 3 − (−10) =
13, x
2
− x
1
= 11 − 3 = 8. Поскольку 8
−1
≡ 3 (mod23), то λ = 13/8 =
Глава 3. Эллиптические кривые                                                85

      Пусть P = (x, y) ∈ E , тогда обратной к точкеP является точка −P =
(x, −y). Сумма P + (−P ) = ∞. Сумма точек P = (x1 , y1 ) и Q = (x2 , y2 ), где
P 6= −Q, вычисляется по формулам:

               x3 = λ2 − x1 − x2
               y3 = λ(x1 − x3 ) − y1
                   (
                      y2 −y1
                                                                          (3.59)
                      x2 −x1 , если P 6= Q,
               λ=     3x21 +a
                       2y1 если P = Q


      Группа точек эллиптической кривой над полем Fq обозначается
символом E(Fq ), а ее мощность (количество элементов) символом #E(Fq ).
Известно, что E(Fq ) ∼
                     = Cn ⊕ Cn , где Cn - циклическая группа порядка n,
                            1      1

n2 делит n1 , и n2 делит q − 1.

      Пример. Пусть E(Fq ) - группа точек кривой y 2 = x3 +x+1 над полем
F23 . Эта группа является циклической с генератором P (0, 1). Рассмотрим все
кратные kP точки P :

    P (0, 1)            2P = (6, −4)      3P = (3, −10)   4P = (−10, −7)
    5P = (−5, 3)        6P = (7, 11)      7P = (11, 3)    8P = (5, −4)
    9P = (−4, −5)       10P = (12, 14) 11P = (1, −7)      12P = (−6, −3)
    13P = (9, −7)       14P = (4, 10)     15P = (9, 7)    16P = (−6, 3)
    17P = (1, 7)        18P = (12, −4) 19P = (−4, 5)      20P = (5, 4)
    21P = (11, −3)      22P = (7, −11) 23P = (−5, −3) 24P = (10, 7)
    25P = (3, 10)       26P = (6, 4)      27P = (0, −1)   28P = (∞)

      Таким образом, данная кривая содержит 28 точек. Порядок точки A
— это наименьшее натуральное число k такое, что kA = ∞. Порядок любой
точки является делителем порядка числа точек, поэтому, порядок любой
точки на данной кривой принадлежит множеству {1, 2, 4, 7, 14, 28}.

      Пример. Найти сумму точек 3P = (3, −10) и 7P = (11, 3).

      Решение. Вычислим λ = (y2 − y1 )/(x2 − x1 ): y2 − y1 = 3 − (−10) =
13, x2 − x1 = 11 − 3 = 8. Поскольку 8−1 ≡ 3 (mod 23), то λ = 13/8 =

Страницы