# Rabin cryptosystem with 1 mod 4

We have p and q which are distinct primes congruent to 1 mod 4. Then we have n = p*q.

Do you know any algorith for calculating square roots for the decryption in this case? I'm asking for some explanation how to calculate or some pseudocode. Thanks in advance

• Anything precise that you do not get in algorithm 3.44 of the HAC? – fgrieu Apr 20 '15 at 18:42
• Square a is our cipher in en.wikipedia.org/wiki/Rabin_cryptosystem#Decryption? How to tell if b is quadratic non-residue mod p? Is it enough to compute b from equation in Algorithm 3.39 point 1? – John Eithman Apr 20 '15 at 19:38
• If you are lucky, $p\equiv q\equiv5\pmod8$ and you can use Alg 3.37. Otherwise, you have to use Alg 3.39 for $r$ or/and $s$; in its point 1, you need Alg 2.149 in order to compute the Jacobi symbol $\Big({b^2-4a\over p}\Big)$. – fgrieu Apr 20 '15 at 20:52
• There is a a new solution for constraints m={13,20,57,64} in Michael O. Rabin Cryptosystem(ijser.org/…) - disclosure, I'm the author. – Shamim biswas Jun 24 '19 at 13:53