Chinese Remainder Theorem -- Rabin Cryptosystem... how to decrypt?!
there are too many websites that use tons of jargons and tons of copy and pasted stuff without showing any workings or useful examples, so here i am.
this is what i understand of the Rabin Cryptosystem. do correct me if im wrong.
p and q are primes.
p = 11, q = 13
n = pq = 143
To encrypt a message m = 15, the cipher c:
c = 15^2 mod 143
= 82 mod 143
To decrypt the message, i will need
mp = sqrt(c) mod p
= sqrt(82) mod 11
mq = sqrt(c) mod p
= sqrt(82) mod 13
how do i get the values of mp and mq where they must be integers?
at the moment, im brute forcing the numbers by calculating (x = c + mod + mod + ...) until i find that sqrt(x) is an integer. is there an algorithm that does this in a more efficient manner?