Package de.tilman_neumann.jml.quadraticResidues

Class QuadraticResiduesMod2PowN

  • public class QuadraticResiduesMod2PowN
extends Object
    Methods to generate quadratic residues or test for quadratic residuosity modulus 2^n.
    Author:
    Tilman Neumann

    • Constructor Detail

      • QuadraticResiduesMod2PowN

        public QuadraticResiduesMod2PowN()

    • Method Detail

      • getNumberOfQuadraticResiduesMod2PowN

        public static long getNumberOfQuadraticResiduesMod2PowN​(int n)
        Compute A23105(n), the number of distinct quadratic residues mod 2^n, via the formula by David S. Dodson in http://oeis.org/search?q=A023105.
        Parameters:
        n - The power of 2.
        Returns:
        Number of distinct quadratic residues mod 2^n

      • isQuadraticResidueMod2PowN

        public static boolean isQuadraticResidueMod2PowN​(BigInteger a,
                                                 int n)
        Computes if 'a' is a quadratic residue modulo 2^n. Iterative implementation for BigIntegers.
        Parameters:
        a - argument
        n - exponent of the modulus m=2^n
        Returns:
        true if 'a' is a quadratic residue modulo 2^n

      • isQuadraticResidueMod2PowN_v1

        public static boolean isQuadraticResidueMod2PowN_v1​(long a,
                                                    int n)
        Computes if 'a' is a quadratic residue modulo 2^n. Iterative implementation for longs.
        Parameters:
        a - argument
        n - exponent of the modulus m=2^n
        Returns:
        true if 'a' is a quadratic residue modulo 2^n

      • isQuadraticResidueMod2PowN

        public static boolean isQuadraticResidueMod2PowN​(long a,
                                                 int n)
        Computes if 'a' is a quadratic residue modulo 2^n. Implementation following https://en.wikipedia.org/wiki/Quadratic_residue. Much faster than v1.
        Parameters:
        a - argument
        n - exponent of the modulus m=2^n
        Returns:
        true if 'a' is a quadratic residue modulo 2^n

      • getQuadraticResiduesMod2PowN_testAll_big

        public static List<BigInteger> getQuadraticResiduesMod2PowN_testAll_big​(int n)
        Compute all quadratic residues modulus 2^n.
        Parameters:
        n -
        Returns:
        list of quadratic residue modulus 2^n

      • getQuadraticResiduesMod2PowN_testAll

        public static List<Long> getQuadraticResiduesMod2PowN_testAll​(int n)
        Compute all quadratic residues modulus 2^n.
        Parameters:
        n -
        Returns:
        list of quadratic residue modulus 2^n

      • getQuadraticResiduesMod2PowN_testAll_v2

        public static List<Long> getQuadraticResiduesMod2PowN_testAll_v2​(int n)
        Compute all quadratic residues modulus 2^n.
        Parameters:
        n -
        Returns:
        list of quadratic residue modulus 2^n

      • getQuadraticResiduesMod2PowN

        public static List<Long> getQuadraticResiduesMod2PowN​(int n)
        Compute all quadratic residues modulus 2^n.
        Parameters:
        n -
        Returns:
        list of quadratic residues

      • getQuadraticResiduesMod2PowN

        public static int getQuadraticResiduesMod2PowN​(int n,
                                               long[] array)
        Compute all quadratic residues modulus 2^n. Fast implementation using a single array, not needing reallocations.
        Parameters:
        n -
        array - the array to fill with quadratic residues
        Returns:
        number of quadratic residues modulus 2^n

      • getComplementOfQuadraticResiduesMod2PowN

        public static TreeSet<Long> getComplementOfQuadraticResiduesMod2PowN​(int n)
        Returns the "complement" of quadratic residues modulo 2^n. The complement c of a quadratic residue qr is computed as c = 2^n - qr if qr>0, c = 0 if qr==0. A004215 can be computed based on these sets.
        Parameters:
        n -
        Returns:
        set of complements