I think what you suggest is very close to the pseudo code at https://gmplib.org/devel/, under the header "mpz_powm and mpz_powm_ui". But you suggest several additional refinements.
I wasn't considering of the case when the base is just a single limb, but any time 2 * log(b) <= log(m). These tricks are valuable only for limited exponents; as soon as the exponent is large, the fraction of optimisable initil operatons will become negligible. * One could find the largest k such that u^{2^k-1} fits in a single limb, and process k exponent bits at a time. True. * One could handle powers of 2 specially, with shifts instead of multiplies. Perhaps then with a separate mpn function. * Maybe one could extend this to take advantage of addmul_2, if present. Not sure to follow you here. You mean to use mul_2 for the multply by b (or b^x for some x) and addmul_2 for some clever (non-principal) reduction? * In general, for "small" U of size somewhere between a single limb, and full n limbs, there's got to be some threshold between using euclidean reduction of less than n limbs, to montgomery reduction of n limbs. Makes sense. * Maybe one shouldn't do the n+1 to n reduction as a separate step, but somehow combine it with a montgomery reduction. E.g., one could probably write a pretty efficient function which computes u R B^{-1} (mod M) as an n-limb number. We then get some additional power of B^{-1} (mod M) into the result, but maybe they can be handled efficiently. I need to think more about this... And if we do additional powm functions, with single limb modulo (and possibly large exponent, since reducing it requires the factorization of m), or single-limb exponent, or single-limb base, we get another challenge in naming all the functions. ;-) We need to consult Dijstra on this. :-) I think our overhead for modexp ops with few-limb modulo is currently terrible. But it is not going to be easy to fix this, without resorting to full assembly functions. Torbjörn _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel