Bitcoin Forum
May 28, 2018, 12:26:12 AM
 News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: Recursive version of the elliptic curve multiplication algorithm  (Read 1708 times)
grondilu
Legendary

Offline

Activity: 1134
Merit: 1001

 June 06, 2012, 08:49:29 AM

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.
1527467172
Hero Member

Offline

Posts: 1527467172

Ignore
 1527467172

1527467172
 Report to moderator
1527467172
Hero Member

Offline

Posts: 1527467172

Ignore
 1527467172

1527467172
 Report to moderator
1527467172
Hero Member

Offline

Posts: 1527467172

Ignore
 1527467172

1527467172
 Report to moderator
"Bitcoin: mining our own business since 2009" -- Pieter Wuille
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
grondilu
Legendary

Offline

Activity: 1134
Merit: 1001

 June 06, 2012, 09:20:43 AM

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

Activity: 504
Merit: 500

 June 06, 2012, 09:25:40 AM

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

Activity: 1134
Merit: 1001

 June 08, 2012, 01:59:42 PM

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]