Cryptography Reference
In-Depth Information
3. 2 = m 1 : Similar to the previous case.
4. 1 = m 3 :Then P, Q, Q + R are collinear; associativity was proved above.
5. 3 = m 1 : Similar to the previous case.
6. 2 = m 2 :Then P + Q must be ± ( Q + R ). If P + Q = Q + R ,then
commutativity plus the above lemma yields
P =( P + Q )
Q =( Q + R )
Q = R.
Therefore,
( P + Q )+ R = R +( P + Q )= P +( P + Q )= P +( R + Q )= P +( Q + R ) .
If P + Q =
( Q + R ), then
( P + Q )+ R = ( Q + R )+ R = −Q
and
P +( Q + R )= P
( P + Q )=
Q,
so associativity holds.
7. 2 = m 3 : In this case, the line m 3 through P and ( Q + R ) intersects E
in ,so P = ( Q + R ). Since ( Q + R ) ,Q,R are collinear, we have
that P, Q, R are collinear and associativity holds.
8. 3 = m 2 : Similar to the previous case.
9. 3 = m 3 :Since 3 cannot intersect E in 4 points (counting multiplici-
ties), it is easy to see that P = R or P = P + Q or Q + R = P + Q or
Q + R = R . The case P = R wastreatedinthecase 2 = m 2 . Assume
P = P + Q . Adding −P and applying Lemma 2.11 yields = Q ,in
which case associativity immediately follows. The case Q + R = R is
similar. If Q + R = P + Q , then adding
Q and applying Lemma 2.11
yields P = R , which we have already treated.
= m j for all i, j , then the hypotheses of the theorem are satisfied, so
the addition is associative, as proved above. This completes the proof of the
associativity of elliptic curve addition.
If i
REMARK 2.12 Note that for most of the proof, we did not use the
Weierstrass equation for the elliptic curve. In fact, any nonsingular cubic
curve would su ce. The identity O for the group law needs to be a point
whose tangent line intersects to order 3. Three points sum to 0 if they lie
on a straight line. Negation of a point P is accomplished by taking the line
through O and P . The third point of intersection is then
P . Associativity
of this group law follows just as in the Weierstrass case.
 
Search WWH ::




Custom Search