Re: big number arithmetic

Thus spake D. J. Bernstein ([email protected]):
> > Karatsuba starts to be useful (depending on the architecture) at
> > 1024 bit numbers and up.
> http://cr.yp.to/highspeed/fall2006.html includes a tutorial on writing
> software for elliptic-curve arithmetic modulo 2^255-19 using 53-bit
> floating-point operations. Here are the titles of three sections:

I have not actually started to look at elliptic curves yet, I was just
speaking about positive integers.

In my measurements, Karatsuba was slower.  I used integer addition and
multiplication, though.  I was planning to try floating point later.
And it makes it a fairer comparison, because all the other bignum
libraries use integer arithmetic, too, as far I know.

My naive Karatsuba implementation was slower than my naive schoolbook
method for 16 word bignums.  I attributed that to it needing to write
temp bignums, while my schoolbook method just writes to memory once,
into the result bignum.  I didn't pursue the matter so far, because gmp
is supposed to use Karatsuba and my schoolbook method clocks less cycles
than gmp, so I've already achieved my goal.

I'm a slow learner, so I'll stick to integers until I have a good RSA
implementation, then I can still learn how to do elliptic curves.

Felix