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...

Printable View

- Jun 10th 2008, 05:56 AMcryptocrowModular Logs
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... - Jun 10th 2008, 06:32 AMMoo
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. - Jun 10th 2008, 06:42 AMcryptocrow
thank's a lot for the detailed info!