We have often discussed how good or bad the Python long integers are,
and today I took a look at the bug tracker to find out if they use
Montgomery reduction to speed up exponentiations.
If you look at the bottom of
you'll see that the patch for Montgomery reduction has not been applied.
The graphs here
show that Montgomery reduction gives a significant performance gain when
we're talking about large numbers.
The GMP library is still twice as fast, so I suggest we move to that.
Other bug reports of interest are:
viff-devel mailing list (http://viff.dk/)