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?