[viff-devel] Big integers in Python

[Martin Geisler]

Hi everybody,

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

  http://bugs.python.org/issue936813

you'll see that the patch for Montgomery reduction has not been applied.
The graphs here

  http://trevp.net/long_pow/

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:

  http://bugs.python.org/issue1814
  http://bugs.python.org/issue4258

-- 
Martin Geisler