Chapter 8

Exercise 2. This software computes the elements of the subgroup U(n)^k = {x^k | x U(n)} of U(n) and its order. Run the program for (n,k) = (27,3), (27,5), (27,7), and (27,11). Do you see a relationship connecting
|U(n)| and |U(n)^k|, phi(n), and k? Make a conjecture. Run the program for (n,k) = (25,3), (25,5), (25,7), and (25,11). Do you see a relationship connecting |U(n)| and |U(n)^k|, phi(n), and k? Make a conjecture. Run the program for (n,k) = (32,2), (32,4), and (32,8). Is your conjecture valid for U(32,16)? If not, restrict your conjecture. Run the program for (n,k) = (77,2), (77,3), (77,5), (77,6), (77,10), and (77,15)? Do you see a relationship among U(77,6) and U(77,2), and U(77,3)? What about U(77,10), U(77,2), and U(77,5)? What about U(77,15), U(77,3), and U(77,5)? Make a conjecture. Use the theory developed in this chapter about expressing U(n) as external direct products of cyclic groups of the form Z_n to analyze these groups to verify your conjectures.

Exercise 3. This software implements the algorithm given in Chapter 8 to express U(n) as an external direct product of groups of the form Z_k. Assume that n is given in prime-power factorization form. Run your program for 3 . 5 . 7, 16 . 9 . 5, 8 . 3 . 25, 9 . 5 . 11, and 2 . 27 . 125. [ NOTE: Please enter the prime-power factorization form with a `period(".")' in between the integers and without any space. Also, this program has been written to accept n as any integer, i.e., instead of entering n in the factored form as 3 . 5 . 7 you could enter 105 . ]

 

Exercise 5. This program implements the RSA public key cryptography scheme. The user enters two primes p and q, an r that is relatively prime to m = lcm(p -1,q -1), and the message M to be sent. Then the program computes the s which is the inverse of r mod m, and the value of M^r mod pq. Then the user can input those numbers and have the computer raise the numbers to the s power to obtain the original input.