Re: Small-base powm

[Niels Möller]

Torbjorn Granlund  writes:

> These tricks are valuable only for limited exponents; as soon as the
> exponent is large, the fraction of optimisable initil operatons will
> become negligible.

The cost of all squarings are about 2*M(n) * exponent size, and in the
case of a small base, there are some savings for the initial squarings.

I think using plain mul and euclidean reduction for the modular
multiplications by the small base will be a win for most exponent sizes.
It makes these operations O(n) each, or O(n * exponent size) total.

Compare to window exponentiation with (large) montgomery-representation,
there the total cost of the modular multiplications are 2*M(n) *
exponent size / k.

So for large n and small base, we have

   esize*(2*M(n) + O(n)), with small euclidean reductions 

   esize*2*M(n) (1+1/k) + precomputation time, for k-bits window

>   * One could handle powers of 2 specially, with shifts instead of
> multiplies.
>   
> Perhaps then with a separate mpn function.

Makes sense.

>   * 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?

Something like that: Allow multiplications by b or b powers of size two
limbs, and for the reduction, compute a two-limb "quotient" and apply
with mpn_addmul_2.

> 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.

I think optimization of the small modulo case is mostly independent of
the small base case.

/Niels


-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Small-base powm

[Torbjorn Granlund]

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