Cryptography Reference
In-Depth Information
y 2 =−
y 1
a 1 x 1
a 3 then P 1 +
P 2 can be computed using the fomula
x 1 +
x 2 +
x 1 x 2 +
a 2 ( x 1 +
x 2 )
+
a 4
a 1 y 1
λ
=
(9.3)
y 1 +
y 2 +
a 1 x 2 +
a 3
instead of equation ( 9.2 ).
Definition 9.1.2 Let E be an elliptic curve over a field
k
and let P
E (
k
). For n
∈ N
+···+
define [ n ] P to be P
P where P appears n times. In particular, [1] is the identity
= O E and [
=
map. Define [0] P
n ] P
[ n ](
P ).
The n -torsion subgroup is
E [ n ]
={
P
E (
k
):[ n ] P
= O E }
.
We write E (
k
)[ n ]for E [ n ]
E (
k
).
Exercise 9.1.3 Let E : y 2
x 3
+
y
=
be an elliptic curve over
F 2 .Let m
∈ N
and P
=
F 2 m ). Show that [2] P
=
( x P ,y P +
( x P ,y P )
E (
1). (We will show in Example 9.11.6 that
this curve is supersingular.)
Exercise 9.1.4 Let E : y 2
x 3
a 2 x 2
+
xy
=
+
+
a 6 be an elliptic curve over
F 2 m for m
N
. Show that there is a point P
=
( x P ,y P )
E (
F 2 m ) if and only if Tr F 2 m / F 2 ( x P +
a 2 +
a 6 /x P )
=
0. Given Q
=
( x Q ,y Q )
E (
F 2 m ) show that the slope of the tangent line to E
at Q is λ Q =
x Q +
y Q /x Q . Show that y Q =
x Q ( λ Q +
x Q ). Hence, show that if P
=
[2] Q
x Q +
a 6 /x Q and Tr F 2 m / F 2 ( a 6 /x P )
then Tr F 2 m / F 2 ( x p )
=
Tr F 2 m / F 2 ( a 2 ), x P =
=
0. Conversely,
Tr F 2 m / F 2 ( a 2 ) and Tr F 2 m / F 2 ( a 6 /x P )
show that if P
E (
F 2 m ) is such that Tr F 2 m / F 2 ( x P )
=
=
0
then P
=
[2] Q for some Q
E (
F 2 m ).
(Point halving) Given P
=
( x P ,y P )
E (
F 2 m ) such that Tr F 2 m / F 2 ( x P )
=
Tr F 2 m / F 2 ( a 2 )
show that th ere are two solutio ns λ Q to the equation λ 2 Q +
λ Q =
x P +
a 2 . For either solution
let x Q = y P +
x P λ Q +
x P , and y Q =
x Q ( λ Q +
x Q ). Show that [2]( x Q ,y Q )
=
P .
k
that have a singular point in the affine
plane (recall that there is a unique point at infinity
One can consider Weierstrass equations over
O E and it is non-singular). By a
change of variable one may assume that the singular point is (0 , 0) and the equation is
C : y 2
. It turns out that the ellipti c
curve group law formulae give rise to a group law on G . There is a morphism over
+
a 1 xy
=
x 3
+
a 2 x 2 .Let G
=
C (
k
)
∪{ O E }−{
(0 , 0)
}
k
1 and the group law on G corresponds to either the additive group G a or the
multiplicative group G m ; see Section 9 of [ 114 ], Section 2.10 of [ 560 ] or Proposition III.2.5
of [ 505 ] for details.
Since an elliptic curve is a projective variety it is natural to consider addition formulae
on projective coordinates. In the applications there are good reasons to do this (e.g., to
minimise the number of inversions in fast implementations of elliptic curve cryptography,
or in the elliptic curve factoring method).
from C to
P
 
Search WWH ::




Custom Search