tg at gmplib.org
Fri Dec 21 10:16:02 CET 2012
Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:
in Section 15.3.5 Jacobi Symbol of the GMP 5.1.0 documentation, one reads:
`mpz_jacobi' and `mpz_kronecker' are currently implemented with a
simple binary algorithm similar to that described for the GCDs (*note
Binary GCD::). They're not very fast when both inputs are large.
Lehmer's multi-step improvement or a binary based multi-step algorithm
is likely to be better.
However according to http://gmplib.org/gmp5.1.html there is now a
subquadratic algorithm for the Kronecker/Jacobi/Legendre symbol.
Thus it seems the documentation is obsolete.
Yep, Marco pointed that out a few days before the release. Alas, we had
no time to fix the documentation. Perhaps we should have put a note
about it obsolescence into the documentation.
By the way, which subquadratic algorithm is implemented?
It reuses Niels' gcd code.
More information about the gmp-bugs