mpz_nextprime

[Niels Möller]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

> with a small base, no need of k-ary modexp. In the REDC domain, instead of
> computing a'*b'/r mod n, where  b' = r*b mod n is the REDC encoding of the
> base b, just compute a'*b mod n.

Right, since the montgomery/redc mapping a <-> a' is linear, the needed
multiply operation is simply

   x --> x * b (mod m)

no matter if x is in montgomery representation or not. The easy way to
do that is x * b followed by euclidean division with a single-limb
quotient. One could perhaps also do x * b / B (mod m), with a
single-limb hensel quotient. One then has to keep track of those powers
of B^-1, and it's unclear to me if they can be handled efficiently
enough to make Hensel-division useful here.

Another trick (I think Marco already mentioned this) may be to find the
largest k such that c = b^k fits in one limb, and compute

  b^e = c^{floor(e/k)] * b^{e mod k}

(and if we handle b = 2 as a special case, one could take k =
GMP_NUMB_BITS, even if c then doesn't quite fit in one limb)).

That will save log_2(k) squarings, so will make a nticable difference
only when the exponent is few limbs. But could be relevant for
millerrabin tests of numbers of a hundred bits or so.

Regards,
/Niels

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