Extending the mpn interface
Bill.Allombert at math.u-bordeaux1.fr
Sun Feb 17 23:21:34 CET 2013
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).
More information about the gmp-devel