$(e,n)$ $\rightarrow$ $(5 ,35)$
$(d,n)$ $\rightarrow$ $(29 ,35)$
encrypted message, $c = 22$
we need to find original message,
Let the original message is p
we know that
$p = c^d$ mod $n$
$= 22^{29}$ mod $35$
Now how to calculate $22^{29}$ mod $35$
Approach 1: simple divide and conquer strategy
divide the power into 2 parts
$22^{14 + 15}$ mod $35$
$22^{14} * 22^{15}$ mod $35$
$( (22^{14}$ mod $35)$ $*$ $(22^{15}$ mod $35) )$ mod $35$ $\because A *B$ mod $n$ = $((A $ mod $n)$ * $(B $ mod $n))$ mod $n$
$22^{14}$ mod $35$
$= 22^7 * 22^7$ mod $35$
$= ( (22^{7}$ mod $35)$ $*$ $(22^{7}$ mod $35) )$ mod $35$
$= (8 *8 )$ mod $35$
$= 64$ mod $35$
$= 29$
Simarly we can do it for $22^{15}$ , we will get $8$
$( 29 $ mod $35)$ $*$ $(8$ mod $35) )$ mod $35
$= ( 29 *8 )$ mod $35
$=22$
Approach 2
Divide the power lets say B in power of 2 by writing it in binary form
$29_{10}$ = ${11101}_{2}$
Start from the rightmost digit, let k = 0, for each digit
1. if the digit is 1 then we need $2^k$, otherwise, we do not
2. add 1 to k and move left to the next digit
$29_{10}$ = $ 2^4 + 2^3 + 2^2 + 2^0$ = $ 16+ 8 + 4 + 1$
$22^{29} \rightarrow 22^{16+8+4+1} \rightarrow 22^{16} * 22^8 * 22^4 *22^1$
$22^{29}$ mod $35$ = $(22^{16} * 22^8 * 22^4 *22^1)$ mod $35$
$22^{16}$ mod $35$ = $1$
$22^{8}$ mod $35$ = $1$
$22^{4}$ mod $35$ = $1$
$22^{1}$ mod $35$ = $22$
$22^{29}$ mod $35$ = $(1 * 1 * 1 *22)$ mod $35$ = $22$