Re: Addition Law and K*P for Montgomery-form elliptic Curves

¬a\/b wrote:
> I have found this
> "
> 1 Let
> k = k0 + k1*2 + k2*2^2 + ... + kr*2^r; ki in [0; 1]; k0 = kr = 1
> be the binary representation of k.
>
> 2) Let S = P, T = 2P, U = -P.
> 3) For i = 1..r do the following:
> when ki = 1
> S := S + T (using U); T := 2T (U is unchanged);
> when ki = 0
> U := U - T (using S); T := 2T (S is unchanged):
> 4) Then we have S = kP.
> "
> but if k0==1 than k is odd: and for k even?
> There is someone that can post this algo in "coodinates form"
> or can explain what does it mean "using U" or -P in a Montgomery-form
> elliptic Curve
>
> if P(x, 1, z) is a point in the Montgomery-form Curve
> E: b*Z*Y^2 = X^3 + a*Z*X^2+ X*Z^2
> what are the coodinates for -P ?

The negative in prime field is (x, p - y) where p is the prime
generating the field and in binary field is (x, x xor y).

Then you can map that to Jacobian by allowing z=1

e.g.

x,y => (x, p - y, 1)

or

x,y => (x, x xor y, 1)

I don't know specifically about Montgomery co-ordinates but it's still
just a matter of mapping affine to whatever form you're using.

So however you go from the input affine point P to what you need in
your algo is how you make -U a point in your algo.

Tom
Received on Fri Dec 23 20:11:15 2005