Package de.tilman_neumann.jml.quadraticResidues

Class QuadraticResiduesModBPowN

java.lang.Object

de.tilman_neumann.jml.quadraticResidues.QuadraticResiduesModBPowN

public class QuadraticResiduesModBPowN
extends Object

Methods to generate quadratic residues or test for quadratic residuosity modulus p^n, where p is an odd prime.

Author:

Tilman Neumann

Constructor Summary

Constructors

Constructor	Description
QuadraticResiduesModBPowN()

Method Summary

Modifier and Type	Method	Description
static List<Long>	getQuadraticResiduesModBPowN(int p, int n)	Compute all quadratic residues modulus p^n.
static List<Long>	getQuadraticResiduesModBPowN_testAll(int p, int n)	Compute all quadratic residues modulus p^n.
static List<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 Detail

QuadraticResiduesModBPowN

public QuadraticResiduesModBPowN()

Method Detail

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 List<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 List<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 List<Long> getQuadraticResiduesModBPowN(int p,
                                                      int n)

Compute all quadratic residues modulus p^n.

Parameters:

p -

n -

Returns:

list of quadratic residues