documentation bug?

Zimmermann Paul Paul.Zimmermann at
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 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?

Best regards,
Paul Zimmermann

More information about the gmp-bugs mailing list