Paul.Zimmermann at loria.fr
Fri Dec 21 07:50:56 CET 2012
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.
By the way, which subquadratic algorithm is implemented?
More information about the gmp-bugs