Class QuadraticResiduesModBPowN

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

public class QuadraticResiduesModBPowN
extends java.lang.Object
Methods to generate quadratic residues or test for quadratic residuosity modulus p^n, where p is an odd prime.
  • Constructor Summary

    Constructors
    Constructor Description
    QuadraticResiduesModBPowN()  
  • Method Summary

    Modifier and Type Method Description
    static java.util.List<java.lang.Long> getQuadraticResiduesModBPowN​(int p, int n)
    Compute all quadratic residues modulus p^n.
    static java.util.List<java.lang.Long> getQuadraticResiduesModBPowN_testAll​(int p, int n)
    Compute all quadratic residues modulus p^n.
    static java.util.List<java.lang.Long> getQuadraticResiduesModBPowN_testAll_v2​(int p, int n)
    Compute all quadratic residues modulus p^n.
    static boolean isQuadraticResidueModBPowN​(long a, int p, int n)
    Computes if 'a' is a quadratic residue modulo p^n.
    static boolean isQuadraticResidueModBPowN_v2​(long a, int p, int n)
    Implementation following https://en.wikipedia.org/wiki/Quadratic_residue.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • QuadraticResiduesModBPowN

      public QuadraticResiduesModBPowN()
  • Method Details

    • isQuadraticResidueModBPowN

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

      public static boolean isQuadraticResidueModBPowN_v2​(long a, int p, int n)
      Implementation following https://en.wikipedia.org/wiki/Quadratic_residue.
      Parameters:
      a -
      p -
      n -
      Returns:
      true if 'a' is a quadratic residue modulo p^n
    • getQuadraticResiduesModBPowN_testAll

      public static java.util.List<java.lang.Long> getQuadraticResiduesModBPowN_testAll​(int p, int n)
      Compute all quadratic residues modulus p^n.
      Parameters:
      p -
      n -
      Returns:
      list of quadratic residue modulus p^n
    • getQuadraticResiduesModBPowN_testAll_v2

      public static java.util.List<java.lang.Long> getQuadraticResiduesModBPowN_testAll_v2​(int p, int n)
      Compute all quadratic residues modulus p^n.
      Parameters:
      p -
      n -
      Returns:
      list of quadratic residue modulus p^n
    • getQuadraticResiduesModBPowN

      public static java.util.List<java.lang.Long> getQuadraticResiduesModBPowN​(int p, int n)
      Compute all quadratic residues modulus p^n.
      Parameters:
      p -
      n -
      Returns:
      list of quadratic residues