(gmp.info.gz) Jacobi Symbol

Info Catalog

(gmp.info.gz) Extended GCD

(gmp.info.gz) Greatest Common Divisor Algorithms

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

Info Catalog

(gmp.info.gz) Extended GCD

(gmp.info.gz) Greatest Common Divisor Algorithms