Compute 2735 mod 569 using the exponentiation routine

Question

1. Use the EXTENDEDGCD algorithm to compute the inverse of 74 modulo the prime 167.

2. Implement GENERATELARGEPRIME Using a language or library that supports big integers. Generate a prime within the range 1= 2²⁵⁵ and u = 2²⁵⁶ - 1.

3. Give pseudo code should not be recursive but should instead use a loop.

4. Compute 27³⁵ (mod 569) using the exponentiation routine described in Section 10.4.2. How many multiplications did you have to per-form?