Congruence arithmetic and a toy NTRU cryptosystem

36 Views Asked by At

This is a doubt from a textbook. Suppose $q,f,g\in\mathbb Z$ are positive numbers such that $f<\sqrt{q/2}$, $\sqrt{q/4}<g<\sqrt{q/2}$ and $\gcd(f,q)=1$. We compute the quantity $h\equiv f^{-1}g \mbox{ mod }q$. The text says that we may let $0<h<q$. I believe this is since $f^{-1}$ is a unit and so not a zero divisor.

Next let us take two integers $r,m$ such that $0<m<\sqrt{q/4}; 0<r<\sqrt{q/2}$. Define, $e\equiv rh+m \mbox{ mod }q$. The text says that we may let $0<e<q$. My question is why? Why can't $rh+m$ be a multiple of $q$?