Revision history [back]

It seems you have found two solutions $r_1,r_2$ to the equation $r^2 = c \pmod p$, instead of modulo $n=p^2$.

These can be lifted to solutions of $r^2 = c \pmod n$ as explained in Tonelli's 1891 note:

sage: x1 = r1.powermod(p, n) * c.powermod((n - 2*p + 1)/2, n) % n
sage: x1
64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271753034649923142113830515792268064444518487016929096020442400942507965121543243161654445051643484581747767916266843209412116392813513581705574559159767553746511654597410103495145251789022071249050813249711591476
sage: (x1^2 - c) % n
0
sage: x2 = (-x1) % n
sage: x2
89179848125512992787564462241620177844581389814477898537473698968367979714250257351636037110348977598736309799901497369527812510845450258136902578048921346119523079429281621431693965762644622048754271598699645
sage: (x2^2 - c) % n
0