mpn_redc_n

[tg at gmplib.org]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

  we might use mpn_redc_n in GMP-ECM, depending on tuning results wrt mpn_redc_1,
  mpn_redc_2, and other functions.
  
I presume you've noticed that this function is booming out

   THIS IS AN INTERNAL FUNCTION WITH A MUTABLE INTERFACE.  IT IS ONLY
   SAFE TO REACH THIS FUNCTION THROUGH DOCUMENTED INTERFACES.

?

  However, it seems mpn_redc_n uses the inverse convention for the precomputed
  inverse (ip[] = 1/mp[] mod R^n instead of -1/mp[] mod R^n for redc_[12]).
  
Indeed, but that might change, as it is mutable...

  Would it be possible to use the same convention?
  
I cannot recall the design decisions behind this.

Taking a quick look, without any deeper understanding of the maths, it
seems that we'd get almost the same behaviour if the inverse was
replaced by the additive inverse (in the ring mod B^n).  The two
multiply operations will then yield the corresponding additive inverses,
meaning that we would get a congruent result by replacing mpn_sub_n by
mpn_add_n.  Congruent, but not the exact same.  Presumably, we'd get the
same result (which should be the principal remainder) with a conditional
subtraction just as we today use a conditional addition.

Niels and Marco might have some comments; they were involved in the
design around this,
  

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