Tag Info

New answers tagged


Since n = pq, then when an integer modulo n is a square, then it has (in general) four square roots. This can be seen by reasoning modulo p and modulo q: a square has two roots modulo p, and two roots modulo q, which makes for four combinations. More precisely, modulo a prime p, if y has a square root x, it also has another square root which is -x. The same ...


After another 5 minutes of thought, I think I solved my own problem. Choose an arbitrary message m, compute c=m^2 % n and submit c and n to the Rabin oracle. If you repeat this enough times (by which I mean probably within 2 iterations) you will choose m in such a way that the oracle gives you ± the other root, which you can then use to factor n.


Take a random positive integer $r<N$ and solve $x^2\equiv r \mod N.$ Let $x_1,x_2$ its roots. There are solutions if $r$ is quadratic residue mod N. If r is not quadratic residue you choose another $r.$ Then compute $\gcd(x_1-x_2,N)=p \ \text{or}\ q.$

Top 50 recent answers are included