Montgomery Precompute?

[Torbjörn Granlund]

EvaOrLew Baxter <lewandeva at hotmail.com> writes:

  My application performs multiple (hundreds of thousands) calls to
  mpz_powm with the same (prime) modulus (tens of thousands of
  digits). In the spirit of Montgomery multiplication, because the
  modulus is constant, I coded my own 'powerMod' using calls to gmp for
  basic multiplication, etc. Some limited experiments showed much slower
  speeds than using mpz_powm. Of course gmp also uses Montgomery math,
  but presumably does not save any precomputations from one call to the
  next.  It would be nice to be able to exploit gmp's use of Montgomery
  math: to have a feature in gmp where the user first indicates the
  constant modulus: mpz_powm_precompute(<modulus>) and then indicates
  with subsequent calls that the precomputed modulus is to be used:
  mpz_pown_using_precomputed(<z>,<x>,<y>) [with implict modulus]. Either
  mpz_powm_precompute would have to return some representation of the
  Montgomery precomputation, and then use that in subsequent calls; or:
  gmp would have to 'remember' the state.  Is thi
   s idea already available via any low-level gmp calls? Is it a feasible new feature?

I agree that we should provide some sort of modulo functions with
precompute features.

Unfortunately, the design of such a function class is non-trivial as
many things determine the best precomputation.

Should just the modulus or also the operands which are to be inputs be
precomputed?  (Montgomery expects the latter, but that's somewhat
irksome.)

How should the user communicate the amount of modulus invariance to be
expected?  Less invariance means a quicker precomputation, more
invariance means an expensice precomputation.

Clearly, Montgomery cannot be used without some help of additional
arithmetic as it requires odd modulus.  Separate computation mod 2^k
will be needed.  So two remainders need to be maintained for every
number...

-- 
Torbjörn
Please encrypt, key id 0xC8601622