Micro-GMP

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> I believe Niels and Marco wrote Mini-GMP.

Right. I put together the initial version (over Christmas break 2011, I
think), and Marco has done most of the later improvements and additions.

> Not only O(n^2) algorithms; addition is actually O(n) while modexp is
> O(n^3)...

As the README describes it:

  The performance target for mini-gmp is to be at most 10 times slower
  than the real GMP library, for numbers of size up to a few hundred
  bits. No asymptotically fast algorithms are included in mini-gmp, so
  it will be many orders of magnitude slower than GMP for very large
  numbers.

And choice of algorithms is then a trade-off between this performance
target and implementation complexity.

I'm not sure what mini-gmp performance actually is; if "10 times slower"
is accurate. But since it uses the C umul_ppmm based on 4 half-limb
products, multiplication (and any other operations dominated by
multiplication) might well be 10 time slower.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.