Extending the mpn interface

[Bill Allombert]

On Sun, Feb 17, 2013 at 09:45:31PM +0100, Niels Möller wrote:
> Bill Allombert <Bill.Allombert at math.u-bordeaux1.fr> writes:
> 
> > Yes, please. What I would really like for PARI/GP:
> > mpn_powm, mpn_divexact, mpn_rootrem
> 
> Those should be fairly straightforward.
> 
> > mpn_halfgcd (this is implemented as part of subquadratic gcd)
> 
> 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.

> What use do you have for half gcd? The two applications I'm aware of are
> subquadratic gcd/gcdext, and "rational reconstruction" (related to
> Axel Thue's Lemma).

Yes, half gcd is essentially equivalent to "rational reconstruction".
GP includes a function bestappr which is implemented using the PARI function
ratlift, whose specification are a bit lengthy:

 *    Given t_INT x, m, amax>=0, bmax>0 such that
 *         0 <= x < m;  2*amax*bmax < m
 *    attempts to find t_INT a, b such that
 *         (1) a = b*x (mod m)
 *         (2) |a| <= amax, 0 < b <= bmax
 *         (3) gcd(m, b) = gcd(a, b)

but in practice, it would be sufficient to handle gcd(a, b)=1 and amax=bmax.
This is a very important algorithm for number theor

> > a way to precondition the modular reduction (this is implemented as part
> > of mpz_powm).
> 
> 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.

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).

Cheers,
Bill.