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

  • $\begingroup$ Anything precise that you do not get in algorithm 3.44 of the HAC? $\endgroup$ – fgrieu Apr 20 '15 at 18:42
  • $\begingroup$ 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? $\endgroup$ – John Eithman Apr 20 '15 at 19:38
  • 1
    $\begingroup$ 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)$. $\endgroup$ – fgrieu Apr 20 '15 at 20:52
  • $\begingroup$ 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. $\endgroup$ – Shamim biswas Jun 24 '19 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.