Montgomery Precompute?

[Paul Zimmermann]

       Dear Lewis,

there are several internal GMP functions that use a precomputed inverse,
see for example mpn/sbpi1_bdiv_q.c in GMP 6.2.1:

/* Computes Q = - U / D mod B^un, destroys U.

   D must be odd. dinv is (-D)^-1 mod B.

*/

void
mpn_sbpi1_bdiv_q (mp_ptr qp,
		  mp_ptr up, mp_size_t un,
		  mp_srcptr dp, mp_size_t dn,
		  mp_limb_t dinv)

but as far as I know, there are not (yet?) exposed to the user.

You can use them, as we do in GMP-ECM for mpn_redc_{1,2,n}, but it is at your
own risk!

Paul Zimmermann

> From: EvaOrLew Baxter <lewandeva at hotmail.com>
> Date: Fri, 16 Apr 2021 11:57:14 +0000
> 
> 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?
> 
> Lewis
> 
> 
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss