TOPICS
Search

Excludent


A method which can be used to solve any quadratic congruence equation. This technique relies on the fact that solving

 x^2=b (mod p)

is equivalent to finding a value y such that

 b+py=x^2.

Pick a few small moduli m. If y mod m does not make b+py a quadratic residue of m, then this value of y may be excluded. Furthermore, values of y>p/4 are never necessary.


See also

Quadratic Congruence Equation

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Excludent." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Excludent.html

Subject classifications