gmp prime testing

[Kevin Ryde]

I wrote:
>
> If you mean an Nx1 gcd, yes that might be an option since it can use
> the faster modexact_1,

Actually I think mpn_modexact_1_odd can be used right now.

It returns c satisfying c*2^x == n mod d, but clearly any factor p of
d also gets c*2^x == n mod p, so p divides n iff p divides c (p and d
both being odd of course).

Don't know why I didn't twig to this in the first place, but in any
event I think mpz/pprime_p.c could be changed from mpn_mod_1 to
MPN_MOD_OR_MODEXACT_1_ODD.

It might even be nice to make the same available to applications doing
divisibility tests, though it'd be a weird function, a sort of
mpz_mod_with_some_2exp_ui or something.


Another low-level idea is that modexact is bound by multiply latency,
so when the multiplier is pipelined or if there's more than one
multiply unit then several divisors could be applied in parallel.  I
guess the same is true of mpn_mod_1, but the modexact is less code and
less registers.