Package de.tilman_neumann.jml.modular

Class JacobiSymbol

  • public class JacobiSymbol
extends Object
    Jacobi symbol. The basic implementation follows [Crandall, Pomerance 2005: Prime numbers]; then we apply some optimizations.
    Author:
    Tilman Neumann

    • Constructor Detail

      • JacobiSymbol

        public JacobiSymbol()

    • Method Detail

      • jacobiSymbol

        public int jacobiSymbol​(BigInteger a,
                        BigInteger m)
        Jacobi symbol J(a|m), with m an odd, positive integer. Highly optimized, using faster quadratic reciprocity.
        Parameters:
        a -
        m - modulus, an odd integer
        Returns:
        J(a|m)

      • jacobiSymbol

        public int jacobiSymbol​(BigInteger a,
                        int m)

      • jacobiSymbol

        public int jacobiSymbol​(int a,
                        BigInteger m)

      • jacobiSymbol

        public int jacobiSymbol​(int a,
                        int m)

      • kroneckerSymbol

        public int kroneckerSymbol​(BigInteger a,
                           BigInteger m)
        The Kronecker symbol K(a|m) generalizes the Jacobi symbol J(a|m) for arbitrary natural numbers m. Note that the Kronecker symbol does not have the same connection to quadratic residues as the Jacobi symbol. In particular, the Kronecker symbol K(a|m) for even m can take values independently on whether a is a quadratic residue or nonresidue modulo m. See https://en.wikipedia.org/wiki/Kronecker_symbol#Properties
        Parameters:
        a -
        m -
        Returns:
        K(a|m)