# Modular Logs

• Jun 10th 2008, 06:56 AM
cryptocrow
Modular 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, 07:32 AM
Moo
Hello,

Quote:

Originally Posted by cryptocrow
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...

\begin{aligned} m & \equiv c^d \ [101] \\
&\equiv (m^3)^d \ [101] \\
&\equiv m^{3d} \ [101] \end{aligned}

So d is such that $m^{3d} \equiv m \ [101]$

Euler's theorem :
$m^{\varphi(n)} \equiv 1 \ [n]$

Here, n=101 and is prime. $\varphi(101)=100$

3d has to be congruent to $1 \mod \varphi(101)$, i.e. $1 \mod 100$
--------
Why ?

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

$100=3 \cdot 33+1 \implies 3 \cdot (-33)=1-100$

$\Longleftrightarrow 3 \cdot (-33) \equiv 1 \mod 100$

$3 \cdot 67 \equiv 1 \mod 100$

$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, 07:42 AM
cryptocrow
thank's a lot for the detailed info!