For this lab, in C++, use the technique on page 485 to calculate the residue of an integer of the form a^k. Your program should prompt the user for a, and k and the modulus. Your program will then print out the residue. The program should loop through 4 times so that it will prompt for 4 different values of a, k and the modulus.. You must use the technique on page 485 for this program.

Use the long long type for intermediate results since raising even small numbers to powers can result in very large numbers. You must use the long long type here.

You can test your code for small numbers and exponents using the C++ modulo (%) but for larger numbers you will not get correct answers as the numbers will be too big. Use the examples in the book to check your code for larger numbers.

8.4 Modular Arithmetic with Applications to Cryptography 485 Example 8.4.4 Computing ak mod n When k Is a Power of 2 Find 1444 mod 713. Solution Use property (8.4.1) to write 1444 = (1442)2. Then 1444 mod 713 = (1442)2 mod 713 = (1442 mod 713)2 mod 713 = (20736 mod 713)2 mod 713 because 1442 = 20736 592 mod 713 because 20736 mod 713 = 59 = 3481 mod 713 because 592 = 3481 because 3481 mod 713 = 629. 629 Example 8.4.5 Computing ak mod n When k Is Not a Power of 2 Find 1243 mod 713. Solution First write the exponent as a sum of powers of 2: 43 = 23 +23+2+1= 32 +8+2 +1. Next compute 122 for k = 1, 2, 3, 4, 5. 12 mod 713 = 12 122 mod 713 = 144 124 mod 713 = 1442 mod 713 = 59 by Example 8.4.4 128 mod 713 = 592 mod 713 = 6 29 by Example 8.4.4 1216 mod 713 = 6292 mod 713 = 639 by the method of Example 8.4.4 1232 mod 713 = 6392 mod 713 = 485 by the method of Example 8.4.4 By property (8.4.2), 1243 = 1232+8+2+1 = 1232. 128. 122.121. Thus, by Corollary 8.4.4, 1243 mod 713 = {(1232 mod 713). (128 mod 713)(122 mod 713). (12 mod 713)} mod 713. By substitution, 1243 mod 713 = (485.629.144.12) mod 713 527152320 mod 713 = 48