Elliptic curves - Mathematics of Public Key Cryptography - page 169

maps to

(1 /w ) V 2 U 3 ( a 2 /w ) U 2 = + + U.

a 2 /w,B

Taking A = = 1 /w ∈ k gives the result.

Conversely, suppose By 2 x 3 Ax 2

= + + x is a Montgomery model of an elliptic curve

. Multiplying though by B 3 gives ( B 2 y ) 2 ( Bx ) 3 AB ( Bx ) 2 B 2 ( Bx ) and so

over k = + +

( Bx,B 2 y ) satisfies the Weierstrass equation V 2 U 3 ABU 2 B 2 U . Taking ( U,V ) = = + +

B 2 a 2 = 0 one can check that the conditions in the statement of the

Lemma hold (the polynomial F ( x ) has the root 0, and a 4 =

AB,a 4 = and a 6 =

B 2 is a square).
The maps extend to the projective curves and map (0 : 1 : 0) to (0 : 1 : 0). The fact that
they are group homomorphisms follows from a generalisation of Theorem 9.2.1 .

When the conditions of Lemma 9.12.4 hold we say that the elliptic curve E can be
written in Montgomery model. Throughout this section, when we refer to an elliptic curve
E in Montgomery model, we assume that E is specified by an affine equation as in
equation ( 9.13 ).

( x 2 ,y 2 ) be points on the elliptic curve By 2

Lemma 9.12.5 Let P 1 = ( x 1 ,y 2 ) ,P 2 = =

x 3 Ax 2 + + x such that x 1 = x 2 and x 1 x 2 = 0 . Then P 1 + P 2 = ( x 3 ,y 3 ) where

x 1 y 2 ) 2 / ( x 1 x 2 ( x 2 − x 1 ) 2 ) . x 3 = B ( x 2 y 1 −

Writing P 1 − P 2 = ( x 4 ,y 4 ) one finds

1) 2 / ( x 1 − x 2 ) 2 .

x 3 x 4 = ( x 1 x 2 −

For the case P 2 = P 1 we have [2]( x 1 ,y 1 ) = ( x 3 ,y 3 ) where

( x 1 − 1) 2 / (4 x 1 ( x 1 + x 3 = Ax 1 + 1)) .

Proof The standard addition formula gives x 3 = B (( y 2 − y 1 ) / ( x 2 − x 1 )) 2 − ( A + x 1 + x 2 ),

which yields

x 1 ) 2 By 1 + By 2 − x 1 ) 2

x 3 ( x 2 − = 2 By 1 y 2 − ( A + x 1 + x 2 )( x 2 −

x 1 x 2 + x 1 x 2 + =− 2 By 1 y 2 + 2 Ax 1 x 2 + x 1 + x 2

x 2

x 1 By 1 +

x 1

x 2 By 2 −

= 2 By 1 y 2

x 1 y 2 ) 2 / ( x 1 x 2 ) .

= B ( x 2 y 1 −

x 1 ) 2

Replacing P 2 by − P 2 gives P 1 − P 2 = ( x 4 ,y 4 ) with x 4 ( x 2 − = B ( x 2 y 1 +

x 1 y 2 ) 2 / ( x 1 x 2 ). Multiplying the two equations gives

x 3 x 4 ( x 2 − x 1 ) 4 = B 2 ( x 2 y 1 − x 1 y 2 ) 2 ( x 2 y 1 + x 1 y 2 ) 2 / ( x 1 x 2 ) 2

x 2 By 1
x 1 −

2

x 1 By 2
x 2

=

x 1 )) 2

= ( x 1 x 2 ( x 1 − x 2 ) + ( x 2 −