I am working through an example solution in Nigel Smart's Cryptography: An Introduction, 3E, p. 181, about the encryption and decryption of plaintext in Rabin's cryptosystem. The calculation boils down to some modular arithmetic. Unfortunately, I don't have a lot of experience with that, and my answers are not lining up with his. I'd like some help understanding my mistakes.
Here is the portion of the problem I understand and can replicate.
Let the public and private keys be given by
- $p=127$ and $q=131$,
- $N=16637$ and $B=12345$.
To encrypt $m=4410$ we compute
$$c=m(m+B) \mod{N}=4633$$
My solution matches his so far. I took these steps:
$$c=4410(4410+12345)\mod{16637}$$
$$c=73889550\mod{16637}$$
$$c=4633$$
Here is the part that is giving me trouble.
To decrypt we first compute $$t=B^2/4 + c \mod{N}=1500$$
$1500$ doesn't line up with what I'm getting. Here are the steps I took:
$$t=12345^2/4 + 4633\mod{16637}$$ $$t=152399025/4 + 4633\mod{16637}$$ $$t=38099756.25 + 4633\mod{16637}$$ $$t=38104389.25\mod{16637}$$ $$t=5659.25$$
I know I must be making a simple, very ignorant mistake somewhere, but I just can't see it. What am I doing wrong?
$\!\bmod N\!:\,\ m^2\!+\!bm\!-\!c\equiv 0\iff m \equiv -b/2\pm\sqrt{b^2/4+c},\ $ by the quadratic formula.
You are computing the discriminant $\,b^2/4 + c,\,$ where $\,b^2/4\,$ denotes $\, 4^{-1}b^2\pmod{\!N}$
It's easy to invert $\,4\,$ mod $N\,$ by Inverse Reciprocity $ $ & $\,\color{}N = 16637\equiv 37\equiv \color{}1\pmod{\!4}\ $ so
$\!\!\bmod N\!:\,\ \dfrac{1}4\equiv \dfrac{1\!+\!N(\color{#c00}{-1})}4\equiv \overbrace{\color{#0a0}{-4159}}^{\large 12478},\ $ by $\bmod 4\!:\ 0\equiv 1\!+\!N\color{#c00}x\equiv 1\!+\!x\!\iff\! \color{#c00}{x\equiv -1}$
Plugging that value for $\,1/4\,$ into the discriminant formula yields the claimed result.
Remark $ $ Your answer is correct $\ 5659.25 = 5659+1/4\equiv 5659\color{#0a0}{-4159} \equiv 1500$
However it is not common to use decimals to denote modular fractions (even modular fractions are discouraged by some authors in elementary contexts).