documentation bug?

Torbjorn Granlund tg at
Fri Dec 21 10:16:02 CET 2012

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