When the modulus m is a product of distinct primes, the decryption will always work

April 25, 2020 | 2 min read

As long as $m$ is a product of distinct primes, the decryption will always work even the message $a$ and the modulus $m$ are not relatively prime. i.e.

Proof:

$\because m = p_1p_2 \dots p_r$

$\therefore \phi(m) = (p_1-1)(p_2-1) \cdots (p_r-1)$ (Euler’s phi function formula)

$\therefore ed = 1 + v(p_1-1)(p_2-1) \cdots (p_r-1)$

If $gcd(a, p_i) = 1$, by Fermat’s little theorem, $a^{p_i-1} \equiv 1 \space(\text{mod}\space p_i)$. Then,

If $gcd(a, p_i) \ne 1$, then $gcd(a, p_i) = p_i$ since $p_i$ is a prime number and $gcd(a, p_i) = 1 \space\text{or}\space p_i$ and hence $a$ is a multiple of $p_i$.

$\therefore a^{ed} - a \equiv 0 - 0 \equiv 0 \space(\text{mod}\space p_i)$

So, whether $a$ and $p_i$ are relatively prime or not, we always have

Since $p_i$ are all distinct prime numbers, we have $a^{ed}\equiv a\space ({\text{mod}} \space p_1p_2 \dots p_r)$ and hence $a^{ed}\equiv a\space ({\text{mod}} \space m) \space\forall a \isin \Z$.

Written by Danny Siu who lives in Hong Kong. You should follow him on Twitter

• ← How to build multiple counters using React and Redux
• Pseudoinverse and the shortest solution to least squares →