Exercise 2.5.1 (Find the key of decoding)

Question

Suppose that $b \equiv a^{67} \pmod{91}$, and that $(a,91) = 1$. Find a positive number $\overline{k}$ such that $b^{\overline{k}} \equiv a \pmod{91}$. If $b = 53$, what is $a \pmod{91}$?

Richard Ganaye · Accepted Answer

\begin{proof}
Since $91 = 7 	imes 13$, $$\phi(91) = 91 \left( 1 - \frac{1}{7}ight) \left( 1 - \frac{1}{11}ight) = 6 	imes 12 = 72.$$
With the B\'ezout's algorithm, we obtain
$$43 	imes 67 - 40 	imes 72 = 1,$$
thus 
$$43 	imes 67 \equiv 1 \pmod {72},$$
so $\overline{k} = 43$ is an inverse modulo $\phi(91) = 72$ of $67$.

By Euler theorem, since $a \wedge91 = 1$, $a^{72} \equiv 1 \pmod {91}$,
 $$b^{\overline{k}} = b^{43} \equiv a^{67 	imes 43} = a^{1 + 72 k} \equiv a \pmod {91}.$$

If $b = 53$, using fast exponentiation, $a \equiv b^{\overline{k}} = 53^{43} \equiv 53 \pmod {91}$.

We can explain that $a \equiv b \pmod {91}$. The multiplicative order of $b = 53$ modulo $91$ is $3$:
$$b^3  = 53^3 \equiv 1 \pmod {91}.$$
Therefore
$$a \equiv b^{37} = (b^3)^{12} \cdot b \equiv b  \pmod {91}.$$
The encrypted message $b$ is the original message $a$ for $a = 53$ !
\end{proof}

Exercise 2.5.1 (Find the key of decoding)

Answers

Comments

Exercise 2.5.1 (Find the key of decoding)

Answers

Comments

Add answer