integer multiplication

[Paul Rubin]

geremy condra <debatem1 at gmail.com> writes:
>> Does anyone know what algorithms for integer multiplication does Python use?
>> I am trying to compare it to those used by Sage as it seems like it takes
>> much longer for Python to do large integer multiplication as compared to
>> Sage (anyone know off the top of their heads?)
>> thank you
> Karatsuba multiplication, at least for large integers.

I didn't realize Python used Karatsuba.  The main issue is probably that
Python uses a straightforward portable C implementation that's not
terribly efficient, while Sage might use something like GMP, which uses
carefully tuned assembler code on many processors.  

If you look for the gmpy module, it gives you a way to use gmp from
Python.  In crypto code (lots of 1024 bit modular exponentials) I think
I found gmpy to be around 4x faster than Python longs.

I think for VERY big integers, GMP uses an FFT-based method that's
even faster than Karatsuba.