$(1$ point$)$ The Chinese Remainder Theorem is often used as a way to speed up modular exponentiation. In

this problem we go through the procedure of using CRT$.$

Suppose we want to compute $x^d$modN, where $x=2956,d=3323,$ and $N=5191.$

To use the CRT technique we must know the factorization of $N.$ In the case of this problem, $N=pq$ where

$p=179$ and $q=29.$

Step $1)$

We first compute $x_p=x,$modp and $x_q=x,$modq

$x_p=$

$x_q=$

Step $2)$

We compute the exponents $d_p=$dmodp$-1$ and $d_q=$dmodq$-1.$ Notice that this step uses

Fermat's Little Theorem.

$d_p=$

$d_q=$

Step $3)$

In this stage we do the exponentiation in the smaller groups.

$y_p=x_p^{d_p},$modp$=$

$y_q=x_q^{d_q},$modq$=$

Step $4)$

We now return to the big group using the formula $y=q{c}_p{y}_p+p{c}_q{y}_q$modN.

In this formula, $c_p=q^{-1},$modp and $c_q=p^{-1},$modq.

$c_p=$

$c_q=$

And finally,

$y=$