Class QuadraticResiduesMod2PowN

java.lang.Object
de.tilman_neumann.jml.quadraticResidues.QuadraticResiduesMod2PowN

public class QuadraticResiduesMod2PowN
extends java.lang.Object
Methods to generate quadratic residues or test for quadratic residuosity modulus 2^n.
  • Constructor Details

    • QuadraticResiduesMod2PowN

      public QuadraticResiduesMod2PowN()
  • Method Details

    • 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​(java.math.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 java.util.List<java.math.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 java.util.List<java.lang.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 java.util.List<java.lang.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 java.util.List<java.lang.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 java.util.TreeSet<java.lang.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