Very basic modular example This is a very basic question, but I cannot get it right. I'm working on a basic asymmetric encryption example.

So $(m^e)^d  \equiv m \pmod n$
(at least with the premise of m &lt; n, I suppose)

If I choose:


m = 14   (my message)
n = 19
e = 3
d = 13  -- because $3 \cdot 13 ≡ 1 \pmod{19}$


Then I encrypt
$14^3 ≡ 8 \pmod {19}$

But I decrypt
$8 ^ {13} ≡ 8 \pmod {19}$

What am I doing wrong?



EDIT My logic behind this is:

$m^e ≡ m' \pmod n$

if $e \cdot d≡1 \pmod n$ then

$m'^d ≡ m \pmod n$

Because $(m^e)^d = m^{e \cdot d} ≡ m^1 \pmod n$
Trying to follow as reference Burt Kaliski's The Mathematics of the RSA Public-Key Cryptosystem, the question has the following issues:


The question selects $n=19$ as a prime, rather than as the factor of two distinct primes $p$ and $q$ ($p=5$, $q=11$, $n=55$ in the reference); this is however not disastrous, and we'll adapt the reference by taking $n=p$ and ignoring $q$.
The question uses $d$ such that $e\,d\equiv1\pmod n$, when nothing suggests that in the reference; the reference uses $e\,d\equiv1\pmod L$ with $L=\operatorname{lcm(p-1,q-1)}$, and with our adaptation that becomes $L=n-1$, thus the relation between $e$ and $d$ should be
$$e\,d\equiv1\pmod{(n-1)}$$
The question ignores the stated requirement that $e$ is relatively prime to $p-1$ and $q-1$ (meaning: $e$ shares no prime factor with either $p-1$ or $q-1$); with our adaptation this becomes that $e$ is relatively prime to $n-1$. It follows that $e=3$ is an invalid choice for $n=19$, since $3$ divides both $e=3$ and $n-1=18$.


If we keep $n=19$, we can use $e=5$, find $d$ such that $e\,d\equiv1\pmod{18}$, e.g. $d=11$. Then $c=m^e\bmod p=14^5\bmod19=10$, and $m'=c^d\bmod n=10^{11}\bmod19=14=m$, as expected.
Note: I use $c$ for the ciphertext as in the reference, and $m'$ for the the result of the decryption.

This is an application of Fermat's little theorem, which states that if $p$ is prime, then for all $m$ not divisible by $p$, it holds that $m^{p-1}\equiv1\bmod p$.

Notice that since we chosed $d$ with $e\,d\equiv1\pmod{(n-1)}$, it holds that $e\,d=k(n-1)+1$ for some integer $k$.

Now, the way we computed $m'$, it holds that
$$\begin{align}m'&amp;\equiv c^d&amp;\pmod n&amp;&amp;\text{ using }m'=c^d\bmod n\\
&amp;\equiv{(m^e)}^d&amp;\pmod n&amp;&amp;\text{ using }c=m^e\bmod n\\
&amp;\equiv m^{e\,d}&amp;\pmod n\\
&amp;\equiv m^{k(n-1)+1}&amp;\pmod n&amp;&amp;\text{ using }e\,d=k(n-1)+1\\
&amp;\equiv {(m^{n-1})}^k\,m&amp;\pmod n\\
&amp;\equiv 1^k\,m&amp;\pmod n&amp;&amp;\text{ using FLT}\\
&amp;\equiv m&amp;\pmod n\\
\end{align}$$
Note: when using the FLT, we rely on $n$ prime, and $m$ not divisible by $n$, which holds.

Since $m'=c^d\bmod n$ it holds that $0\le m'&lt;n$. We have $0&lt;m&lt;n$ and $m'\equiv m\pmod n$, hence $m'=m$ Q.E.D.



An incorrect assumption made in the question's reasoning is that it would hold that $m^i\bmod n=m^{(i\bmod n)}\bmod n$; that's false in general, and a proof is given by the computations in the question.

What really holds is that $m^i\bmod n=m^{(i\bmod\lambda(n))}\bmod n$ where $\lambda$ is the Carmichael function, and $m$ is coprime with $n$ or $n$ is square-free. The later holds in RSA. In the reference $n=p\,q$ with $p$ and $q$ distinct primes, and $\lambda(n)=L=\operatorname{lcm}(p-1,q-1)$.



Standard notation, used in this answer (but not the reference, which omits parenthesis in the first notation): for $w&gt;0$


$u\equiv v\pmod w$ means that $w$ divides $u-v$
$u=v\bmod w$ means that $w$ divides $u-v$ and $0\le u&lt;w$.