# Modular arithmetic in Rabin's cryptosystem

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).