Montgomery Precompute?

EvaOrLew Baxter lewandeva at hotmail.com
Fri Apr 16 11:57:14 UTC 2021


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 this idea already available via any low-level gmp calls? Is it a feasible new feature?

Lewis




More information about the gmp-discuss mailing list