15.3.5 Jacobi Symbol

[This section is obsolete. The current Jacobi code actually uses a very efficient algorithm.]

mpz_jacobi and mpz_kronecker are currently implemented with a simple binary algorithm similar to that described for the GCDs (see 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.

When one operand fits a single limb, and that includes mpz_kronecker_ui and friends, an initial reduction is done with either mpn_mod_1 or mpn_modexact_1_odd, followed by the binary algorithm on a single limb. The binary algorithm is well suited to a single limb, and the whole calculation in this case is quite efficient.

In all the routines sign changes for the result are accumulated using some bit twiddling, avoiding table lookups or conditional jumps.