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 ?

It might help to notice that the algorithm you present is
not particularly tied to elliptic curves: it is a general-
purpose algorithm for multiplying something (P) by any odd
integer > 0 (k) using only the operations of adding, subtracting,
and doubling. The following Python program demonstrates its
use to multiply integers:

#! /usr/bin/env python

def multiply( k, P ):
  """Return k * P, for k odd."""

  S = P
  T = 2 * P
  U = -P
  k = k / 2
  while k > 0:
    if k & 1:
      S = S + T
    else:
      U = U - T
    T = 2 * T
    k = k / 2
  return S

def test( i, j ):
  expected = i * j
  got = multiply( i, j )
  print "%3d * %3d = %d vs %d:" % ( i, j, got, expected ),
  if got == expected: print "... OK"
  else: print " ******** bad"

if __name__ == "__main__":
  for i in range( 1, 20, 2 ):
    for j in range( 1, 20 ):
      test( i, j )

-- 
Peter Pearson
To get my email address, substitute:
nowhere -> spamcop, invalid -> net