Extending the mpn interface

[Niels Möller]

Bill Allombert <Bill.Allombert at math.u-bordeaux1.fr> writes:

>> Here, I think we may need to spend some effort on the interface. Have
>> you looked at the currently internal hgcd functions?
>
> Not in any detail.

I'm not going to look into a public hgcd function right away, but when I
(or someone else) do, feedback on the current internal interface will be
very useful.

>> I'm not entirely sure what you mean, but on the mpn level, I think it
>> makes sense to make some redc functions public.
>
> GMP probably do not use redc for large modulus.

For powm, I think it uses redc (in the flavor redc_n) also for very large
(odd) modulo, even if the difference to plain euclidean division is
going to be pretty small.

> What I need is a pair of function, fun1, fun2 so that
> fun2(a,fun1(n),n) = a mod n
> and fun2 is faster than mpn_tdiv_qr(a,n) (once fun1(n) is known).

Ok, that sounds more like the invariance interface which has been
discussed for a long time, unfortunately with little progress. Your fun1
would be a reciprocal, floor(2^k / n) for some suitable k, probably
somewhere between 3/2 and 2 times the bitsize of n. And for n of
moderate size, I think using an invariant reciprocal like this would be
slower than redc, if you do a sequence of modular multiplications like
for powm.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.