To solve general quadratic modulo equations

boggart0803 29 Mar 2009 22:21

As Andy mentioned in the class, to solve general quadratic modulo equations is equivalent to solve $x^2 \equiv t$mod $p$.

Suppose the original equation is $ax^2+bx+c\equiv k$mod $p$

if $p \neq 2$, this equation is equivalent to $4ax^2+4bx+4c\equiv 4k$mod $p$

since $p\nmid a$, we can multiply both sides by the inverse of $a$, call it $a'$

hence $4x^2+4a'bx+4a'c\equiv 4a'k$mod $p$

we get $(2x+a'b)^2-4a'^2b^2+4a'c\equiv 4a'k$mod $p$

therefore $(2x+a'b)^2\equiv 4a'^2b^2-4a'c+4a'k$mod $p$

let $2x+a'b=y$, $4a'^2b^2-4a'c+4a'k=t$

the equation is just $y^2 \equiv t$mod $p$

since $y=2x+a'b$, and $2\nmid p$, to solve $y$ is the same as to solve $x$!!

However, I'm more interested in how the modulus can be reduced into prime moduli