Jacobi/Legendre/Kronecker

[Zimmermann Paul]

       Niels,

> From: nisse at lysator.liu.se (Niels Möller)
> Date: Mon, 17 Dec 2012 16:53:52 +0100
> 
> Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:
> 
> > Assume one wants to compute the Legendre symbol (A/P) for P an unsigned long
> > (and A too). What is more efficient?
> >
> > 1) use mpz_kronecker_ui, which forces to convert A to unsigned long
> >
> > 2) use mpz_ui_kronecker, which forces to convert P to unsigned long
> >
> > 3) use mpz_legendre, which forces to convert both A and P to unsigned long
> 
> I think all three should end up in mpn_jacobi_base, where most of he time should
> be spent.

unfortunately mpn_jacobi_base is not in the public interface...

> I haven't thought about the interface issues, I guess public functions
> with single limb (or unsigned long) inputs would make sense for both
> jacobi and gcd.

agreed.

> Ah, and one other comment. In GMP, mpz_kronecker, mpz_jacobi and
> mpz_legendre are all different names for the same function, so none is
> simpler than the other.

this is strange, since from the documentation mpz_jacobi(A,15) should work
but mpz_legendre(A,15) should be undefined. If no check is done at all, I
do not see why there are 3 different functions.

Paul