Recursive version of the elliptic curve multiplication algorithm

[grondilu]

As I was trying to speeden my Perl6 bitcoin library, I realized something that is worth mentionning, imho.

In the elliptic curve arithmetics library, the implementation of "mult" is kind of weird and tough to understand.  Here is the relevant part in Python:

Code:

def __mul__( self, other ):
    """Multiply a point by an integer."""

    def leftmost_bit( x ):
      assert x > 0
      result = 1L
      while result <= x: result = 2 * result
      return result // 2

    e = other
    if self.__order: e = e % self.__order
    if e == 0: return INFINITY
    if self == INFINITY: return INFINITY
    assert e > 0

    # From X9.62 D.3.2:

    e3 = 3 * e
    negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )
    i = leftmost_bit( e3 ) // 2
    result = self
    # print "Multiplying %s by %d (e3 = %d):" % ( self, other, e3 )
    while i > 1:
      result = result.double()
      if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self
      if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self
      # print ". . . i = %d, result = %s" % ( i, result )
      i = i // 2
    
    return result

Well, I don't know about you, but to me, this is ugly.

I love recursive functions, so whenever I think I can write one, I think hard about how to actually do it.

It appeared to me that this one is a good candidate.   Here is what I'd do:

Code:

def __mul__( self, other ):
    """Multiply a point by an integer."""

    e = other
    if self.__order: e = e % self.__order
    if e == 0: return INFINITY
    if self == INFINITY: return INFINITY
    assert e > 0

    if e == 1:  return self
    if e == 2:  return self.double
    assert e > 2
    if e%2 == 0:  return (e/2 * self).double
    return self + (e/2 * self).double

Well, I didn't try this particular one because I don't like python, but the same idea worked fine with my perl implementation for instance:

Code:

sub mult {
    no warnings qw(recursion);
    my $k = shift;
    my $u = shift;
    return
    $k == 1   ? $u :
    $k == 2   ? double $u :
    $k%2 == 0 ? double mult $k/2, $u :
    add $u, double mult $k/2, $u
    ;
}

To me it's kind of cool.

[grondilu]

To me it's kind of cool.

Recursion is cool on paper.

In the real world, unless you have a compiler smart
enough to handle tail recursions properly it's dog slow.

But then again, it's Perl and Python, so who cares about
speed in the first place.

The Perl6 developpers are working hard on dealing with tail recursion (I think it's done already in rakudo).  I guess the Python team is concerned about that too.

Also, the maximum amount of recursive call here is 256.  That sure is a lot but it is capped so it should be fine I guess.

[realnowhereman]

It's an interesting exercise, but since all recursion can be converted to iteration (and vice versa), and iteration tends not to have any stack problems, you're almost always better converting your recursive algorithm to iterative (plus compilers are much better at unrolling iterative loops for optimisation purposes).

(Note: I haven't studied your code well enough to know whether this is one of the cases outside the "almost always", but I'd be surprised if it weren't)

[grondilu]

I finally wrote a non-recursive, yet much simpler code:

Code:

sub mult {
    my $k = shift;
    my $point = shift->clone;
    my $result = EC::Point->horizon;
    for (; $k > 0; $point = double($point), $k /= 2) {
        $result += $point if $k%2 == 1;
    }
    return $result;
}

To me it is much better than messing aroung with binary shift operators.