Torbjörn, > With k-ary modexp, the number of multiplications is log2(n)/k, > while the number of squarings are log(n). Therefore a small b will not > make a huge difference. > > As Marco points implies, one may handle some special values like b = 2 > also in REDC coding and still not pay the price of a full > multiplication.
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. Another trick is to use a base b such that b' is small, then you don't even need to modify the REDC code (assuming it recognizes small multipliers). Paul _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
