Bitcoin Forum
December 10, 2016, 10:34:43 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Recursive version of the elliptic curve multiplication algorithm  (Read 1597 times)
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
June 06, 2012, 08:49:29 AM
 #1


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.
1481409283
Hero Member
*
Offline Offline

Posts: 1481409283

View Profile Personal Message (Offline)

Ignore
1481409283
Reply with quote  #2

1481409283
Report to moderator
1481409283
Hero Member
*
Offline Offline

Posts: 1481409283

View Profile Personal Message (Offline)

Ignore
1481409283
Reply with quote  #2

1481409283
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481409283
Hero Member
*
Offline Offline

Posts: 1481409283

View Profile Personal Message (Offline)

Ignore
1481409283
Reply with quote  #2

1481409283
Report to moderator
1481409283
Hero Member
*
Offline Offline

Posts: 1481409283

View Profile Personal Message (Offline)

Ignore
1481409283
Reply with quote  #2

1481409283
Report to moderator
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
June 06, 2012, 09:20:43 AM
 #2


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
Hero Member
*****
Offline Offline

Activity: 504



View Profile
June 06, 2012, 09:25:40 AM
 #3

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)

1AAZ4xBHbiCr96nsZJ8jtPkSzsg1CqhwDa
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
June 08, 2012, 01:59:42 PM
 #4

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.
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!