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