good morning,
encrypt: c = m^3 (mod 101)
decrypt: m = c^d (mod 101)
how would i solve for d (with the most efficient method by hand)?
thanks...
Hello,
$\displaystyle \begin{aligned} m & \equiv c^d \ [101] \\
&\equiv (m^3)^d \ [101] \\
&\equiv m^{3d} \ [101] \end{aligned}$
So d is such that $\displaystyle m^{3d} \equiv m \ [101]$
Euler's theorem :
$\displaystyle m^{\varphi(n)} \equiv 1 \ [n]$
Here, n=101 and is prime. $\displaystyle \varphi(101)=100$
3d has to be congruent to $\displaystyle 1 \mod \varphi(101)$, i.e. $\displaystyle 1 \mod 100$
--------
Why ?
$\displaystyle m^{3d}=m^{1+100k}=m \cdot \left(m^{100}\right)^k=m \mod 101$
--------
So we want to find the inverse of 3 modulo 100.
$\displaystyle 100=3 \cdot 33+1 \implies 3 \cdot (-33)=1-100$
$\displaystyle \Longleftrightarrow 3 \cdot (-33) \equiv 1 \mod 100$
$\displaystyle 3 \cdot 67 \equiv 1 \mod 100$
$\displaystyle d=67$
But you have to be careful, because either I've confused myself, either this is a particular case. In general, the number which would be at the same place as 101 is rarely prime.