mini-gmp: mpz_congruent_p and mpz_probab_prime_p

[Niels Möller]

Hi,

Nikos Mavrogiannopoulos recently tried building Nettle, using mini-gmp
for all bignum operations. As far as I understand, dnssec support has
(recently?) been added to dnsmasq, using Nettle and GMP. I think GMP is
used here only for *verifying* signatures; no private keys involved and
no issues with side-channel leaks.

And dnsmasq is often used on small "home routers" where the footprint of
GMP is a bit too large to be comfortable. Anyway, after some hacking,
Nikos got this mostly working, with a performance difference less than a
factor of 10. There were two GMP calls in Nettle which were missing in
mini-gmp: mpz_congruent_p and mpz_probab_prime_p.

I think it would make sense to add mpz_congruent_p to mini-gmp, and I
think a subtraction followed by mpz_divisible_p is a good way to do it.

I'm not sure what to do about mpz_probab_prime_p. One could implement it
fairly simply as a Miller-Rabin test with no trial division (and some
deterministically selected bases?!), or do some very limited trial
division, say, checking for even numbers, and collecting the odd primes
that fit in 32-bits. But I doubt it's possible to do a "small"
implementation with an average running time at most 10 times worse than
GMP's code with pretty sophisticated trial division.

Or just not support it, and in the case of Nettle, key generation
functions could be disabled when building with mini-gmp.

What do you think?

Regards,
/Niels


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