Return to Answer

In $(m^e)^d\equiv m\pmod n$, as long as $e$ and $d$ are positive integers, the fragment $(m^e)^d$ means $m$ raised to the power $e$, then raised to the power $d$, that is $$\underbrace{{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}\times\ldots\times{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}}_{d\text{ terms}}$$ and (by associativity of multiplication) that's equal to $m^{(e\times d)}$.

The notation $u\equiv v\pmod n$ means $u-v$ is some multiple of $n$, but does not specify a range for either $u$ or $v$. Therefore, $(m^e)^d\equiv m\pmod n$ means that if we evaluated $\left(\left(m^e\right)^d\right)-m$ we'd obtain some multiple of $n$.

In contrast, the notation $u=v\bmod n$ or equivalently $v\bmod n=u$ mean $u\equiv v\pmod n$ and $0\le u<n$, thus uniquely specifies the integer $u$ as a function of $v$ and $n$.

Therefore, $(m^e)^d\equiv m\pmod n$ conveys less information than does $(m^e)^d\bmod n=m$, because only the second states that $0\le m<n$.

If we know $0\le m<n$ (e.g. because that's an enforced restriction), then $(m^e)^d\equiv m\pmod n$ and $(m^e)^d\bmod n=m$ are equivalent.

In the computation of ciphertext $c$ from $m$, $e$, $n$ in textbook RSA, we want to write $c=m^e\bmod n$ which fully specifies $c$, not $c\equiv m^e\pmod n$ which allows several $c$, including $c=m^e$ which makes it trivial to find $m$ from $c$, $e$, $n$.

In order to actually compute $c$ with $c=m^e\bmod n$ from $m$, $e$, $n$ we can limit to integers less than $n^2$ and at most $2\log_2e$ multiplication steps, which are practical requirement to make that computation feasible. E.g. $e=17=2^4+1$, we'd need only $5$ multiplications followed by Euclidean division by $n$ keeping the remainder, by computing: $$\begin{align} m_2&\gets(m\times m)\bmod n\\ m_4&\gets(m_2\times m_2)\bmod n\\ m_8&\gets(m_4\times m_4)\bmod n\\ m_{16}&\gets(m_8\times m_8)\bmod n\\ c&\gets(m_{16}\times m)\bmod n\\ \end{align}$$

In $(m^e)^d\equiv m\pmod n$, as long as $e$ and $d$ are positive integers, the fragment $(m^e)^d$ means $m$ raised to the power $e$, then raised to the power $d$, that is $$\underbrace{{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}\times\ldots\times{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}}_{d\text{ terms}}$$ and (by associativity of multiplication) that's equal to $m^{(e\times d)}$.

The notation $u\equiv v\pmod n$ means $u-v$ is some multiple of $n$, but does not specify a range for either $u$ or $v$. Therefore, $(m^e)^d\equiv m\pmod n$ means that if we evaluated $\left(\left(m^e\right)^d\right)-m$ we'd obtain some multiple of $n$.

In contrast, the notation $u=v\bmod n$ or equivalently $v\bmod n=u$ mean $0\le u<n$ and $u\equiv v\pmod n$ (as defined above), thus uniquely specifies the integer $u$ as a function of $v$ and $n$.

Therefore, $(m^e)^d\equiv m\pmod n$ conveys less information than does $(m^e)^d\bmod n=m$, because only the second states that $0\le m<n$.

If we know $0\le m<n$ (e.g. because that's an enforced restriction), then $(m^e)^d\equiv m\pmod n$ and $(m^e)^d\bmod n=m$ are equivalent.

In the computation of ciphertext $c$ from $m$, $e$, $n$ in textbook RSA, we want to write $c=m^e\bmod n$ which fully specifies $c$, not $c\equiv m^e\pmod n$ which allows several $c$, including $c=m^e$ which makes it trivial to find $m$ from $c$, $e$, $n$.

In order to actually compute $c$ with $c=m^e\bmod n$ from $m$, $e$, $n$ we can limit to integers less than $n^2$ and perform at most $2\log_2e$ multiplication steps. E.g. for $e=17=2^4+1$, we'd need only $5$ multiplications followed by Euclidean division by $n$ keeping the remainder, by computing: $$\begin{align} m_2&\gets(m\times m)\bmod n\\ m_4&\gets(m_2\times m_2)\bmod n\\ m_8&\gets(m_4\times m_4)\bmod n\\ m_{16}&\gets(m_8\times m_8)\bmod n\\ c&\gets(m_{16}\times m)\bmod n\\ \end{align}$$

In $(m^e)^d\equiv m\pmod n$, as long as $e$ and $d$ are positive integers, the fragment $(m^e)^d$ means $m$ raised to the power $e$, then raised to the power $d$, that is $$\underbrace{{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}\times\ldots\times{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}}_{d\text{ terms}}$$ and (by associativity of multiplication) that's equal to $m^{(e\times d)}$.

The notation $u\equiv v\pmod n$ means $u-v$ is some multiple of $n$, but does not specify a range for either $u$ or $v$. Therefore, $(m^e)^d\equiv m\pmod n$ means that if we evaluated $\left(\left(m^e\right)^d\right)-m$ we'd obtain some multiple of $n$.

In contrast, the notation $u=v\bmod n$ or equivalently $v\bmod n=u$ mean $u\equiv v\pmod n$ and $0\le u<n$, thus uniquely specifies the integer $u$ as a function of $v$ and $n$.

Therefore, $(m^e)^d\equiv m\pmod n$ conveys less information than does $(m^e)^d\bmod n=m$, because only the second states that $0\le m<n$.

If we know $0\le m<n$ (e.g. because that's an enforced restriction), then $(m^e)^d\equiv m\pmod n$ and $(m^e)^d\bmod n=m$ are equivalent.

In the computation of ciphertext $c$ from $m$, $e$, $n$ in textbook RSA, we want to write $c=m^e\bmod n$ which fully specifies $c$, not $c\equiv m^e\pmod n$ which allows several $c$, including $c=m^e$ which makes it trivial to find $m$ from $c$, $e$, $n$.

In $(m^e)^d\equiv m\pmod n$, as long as $e$ and $d$ are positive integers, the fragment $(m^e)^d$ means $m$ raised to the power $e$, then raised to the power $d$, that is $$\underbrace{{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}\times\ldots\times{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}}_{d\text{ terms}}$$ and (by associativity of multiplication) that's equal to $m^{(e\times d)}$.

The notation $u\equiv v\pmod n$ means $u-v$ is some multiple of $n$, but does not specify a range for either $u$ or $v$. Therefore, $(m^e)^d\equiv m\pmod n$ means that if we evaluated $\left(\left(m^e\right)^d\right)-m$ we'd obtain some multiple of $n$.

In contrast, the notation $u=v\bmod n$ or equivalently $v\bmod n=u$ mean $u\equiv v\pmod n$ and $0\le u<n$, thus uniquely specifies the integer $u$ as a function of $v$ and $n$.

Therefore, $(m^e)^d\equiv m\pmod n$ conveys less information than does $(m^e)^d\bmod n=m$, because only the second states that $0\le m<n$.

If we know $0\le m<n$ (e.g. because that's an enforced restriction), then $(m^e)^d\equiv m\pmod n$ and $(m^e)^d\bmod n=m$ are equivalent.

In the computation of ciphertext $c$ from $m$, $e$, $n$ in textbook RSA, we want to write $c=m^e\bmod n$ which fully specifies $c$, not $c\equiv m^e\pmod n$ which allows several $c$, including $c=m^e$ which makes it trivial to find $m$ from $c$, $e$, $n$.

In order to actually compute $c$ with $c=m^e\bmod n$ from $m$, $e$, $n$ we can limit to integers less than $n^2$ and at most $2\log_2e$ multiplication steps, which are practical requirement to make that computation feasible. E.g. $e=17=2^4+1$, we'd need only $5$ multiplications followed by Euclidean division by $n$ keeping the remainder, by computing: $$\begin{align} m_2&\gets(m\times m)\bmod n\\ m_4&\gets(m_2\times m_2)\bmod n\\ m_8&\gets(m_4\times m_4)\bmod n\\ m_{16}&\gets(m_8\times m_8)\bmod n\\ c&\gets(m_{16}\times m)\bmod n\\ \end{align}$$

The notation $u\equiv v\pmod n$ means $u-v$ is some multiple of $n$, but does not specify a range for either $u$ or $v$.

In contrast, the notation $u=v\bmod n$ or equivalently $v\bmod n=u$ additionally mean that $0\le u<n$, thus uniquely specifies the integer $u$ as a function of $v$ and $n$.

Therefore, $(m^e)^d\equiv m\pmod n$ conveys less information than does $(m^e)^d\bmod n=m$, because only the second states that $0\le m<n$.

If we know $0\le m<n$ (e.g. because that's an enforced restriction), then $(m^e)^d\equiv m\pmod n$ and $(m^e)^d\bmod n=m$ are equivalent.

In the computation of ciphertext $c$ from $m$, $e$, $n$ in textbook RSA, we want to write $c=m^e\bmod n$ which fully specifies $c$, not $c\equiv m^e\pmod n$ which allows several $c$, including $c=m^e$ which makes it trivial to find $m$ from $c$, $e$, $n$.

In $(m^e)^d\equiv m\pmod n$, as long as $e$ and $d$ are positive integers, the fragment $(m^e)^d$ means $m$ raised to the power $e$, then raised to the power $d$, that is $$\underbrace{{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}\times\ldots\times{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}}_{d\text{ terms}}$$ and (by associativity of multiplication) that's equal to $m^{(e\times d)}$.

The notation $u\equiv v\pmod n$ means $u-v$ is some multiple of $n$, but does not specify a range for either $u$ or $v$. Therefore, $(m^e)^d\equiv m\pmod n$ means that if we evaluated $\left(\left(m^e\right)^d\right)-m$ we'd obtain some multiple of $n$.

In contrast, the notation $u=v\bmod n$ or equivalently $v\bmod n=u$ mean $u\equiv v\pmod n$ and $0\le u<n$, thus uniquely specifies the integer $u$ as a function of $v$ and $n$.

Therefore, $(m^e)^d\equiv m\pmod n$ conveys less information than does $(m^e)^d\bmod n=m$, because only the second states that $0\le m<n$.

If we know $0\le m<n$ (e.g. because that's an enforced restriction), then $(m^e)^d\equiv m\pmod n$ and $(m^e)^d\bmod n=m$ are equivalent.

In the computation of ciphertext $c$ from $m$, $e$, $n$ in textbook RSA, we want to write $c=m^e\bmod n$ which fully specifies $c$, not $c\equiv m^e\pmod n$ which allows several $c$, including $c=m^e$ which makes it trivial to find $m$ from $c$, $e$, $n$.