How to solve such a quadratic congruence equation?

Question

I have the following equation: $y^2 \equiv r^2 \pmod n $

I know the values of y and n, I just need to find the values of r.

Assuming that $y = 12654$ and $n = 79061$, my working is as follows:

$ 12654^2$ mod $79061 = r^2$ mod $79061$

$25191 = r^2$ mod $79061$

The prime factorization of 79061 is $173*457$

Hence,

$r^2 = 25191$ mod $173$ $=>$ $106$ mod $173$

$r^2 = 25191$ mod $457$ $=>$ $56$ mod $457$

So now I have two equations,

$r^2 = 106$ mod $173$ and $r^2 = 56$ mod $457$

I am stuck here, I would appreciate if someone can help me move forward.

I've stumbled upon other similar questions where the answers show that they get rid of the squared but I cannot understand how they do it.

Answer 1

The equation can be rewritten as $(y-r)(y+r)=y^2 -r^2\equiv 0 \pmod n$. Now each of the two factors of $n$ must divide at least one of the factors of $y^2 -r^2$.

Answer 2

You know $r^2$ modulo $p$ and $q$ (the prime factors). There we have exactly two solutions: $y$ and $-y$ modulo $p$ resp. $q$. (we have a field modulo a prime so no more then $2$).

Now the CRT now allows us to combine the $4$ pairs of solutions (corresponding to the 4 possible choices of sign) to $4$ solution modulo $n=pq$.

So e.g. solve the systems $x\equiv -y \pmod p$, $x \equiv y \pmod q$ using the CRT formula (e.g. see wiki, constructive proof) and $x\equiv y \pmod p$, $x \equiv -y \pmod q$ to get the two extra solutions besides the already known solutions $y$ and $-y \pmod{n} \equiv n-y$.

Answer 3

Similar to 'random' comment we have:

$(y-r)(y+r)≡0\mod n$

$n=79061=173\times457$

Following cases can be considered:

a: $y-r=173$ ⇒ $r=y-173=12654-173=12421$

b: $y+r=173$ ⇒ $r=173-12654=-12421$

And we have:

$ 12654^2-(±12421)^2=55\times 79061$

c: $y-r=457$⇒ $r=12654+457=13111$

d: $y+r=457$⇒ $r=-13111$

And we have:

$12654^2-13111^2=148.93...\times79061$

So $r= ±12421$ is acceptable.

Answer 4

$$ 12654^2 - (91542 - 79061 m)^2 = 79061 (-79061 m^2 + 183084 m - 103968) $$ $$ r=91542 - 79061 m $$