Avoiding overflow when encrypting with RSA When encrypting with RSA one calculates $ m^e \pmod n $ by doing the following:

m^e % n


Where $m$ is what we encrypt. Often $e$ is a very big number to make it more difficult to crack.

So how does one avoid overflow when encrypting?
Actually, the fundamental mathematical operation is not
$$
\begin{align}
  \mathbb{N} &amp;\to \mathbb{N} \\
  m &amp;\mapsto (m^e) \bmod n &amp; \text{(elevate to the power of \(e\), divide by \(n\) and take the remainder)} \\
\end{align}
$$
but
$$
\begin{align}
  \mathbb{Z}/n\mathbb{Z} &amp;\to \mathbb{Z}/n\mathbb{Z} \\
  m &amp;\mapsto (m^e) \bmod n &amp; \text{(elevate to the power of \(e\))}\hphantom{\text{, divide by \(n\) and take the remainder}} \\
\end{align}
$$
It is an operation in modulo arithmetic.

In computations, the elements of $\mathbb{Z}/n\mathbb{Z}$ are almost always represented by the representative in the range $[0,n-1]$. Each elementary operation is performed in $\mathbb{N}$, then the result is truncated modulo $n$. For example, if $n$ fits in $k$ machine words, then a multiplication of two elements of $\mathbb{Z}/n\mathbb{Z}$ can be performed by computing the product, which fits in $2k$ machine words, then taking the remainder modulo $n$, yielding a representation of the element of $\mathbb{Z}/n\mathbb{Z}$ that is again in the range $[0,n-1]$ and in particular fits in $k$ words. Taking the exponential of a number involves a series of multiplication, each of which is truncated to $[0,n-1]$ in this way so as to obtain the smallest representative of the element of $\mathbb{Z}/n\mathbb{Z}$.

Even multiplication of two $k$-word numbers can be performed with intermediate values fitting in $k$ words. The naive method is wasteful both in the amount of memory and in that it builds a large number only to divide it afterwards. Methods such as Montgomery multiplication avoid computing a double-size number by reducing the size of the result after each intermediate step in the multiplication.