paul zimmermann <paul.zimmerm...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
