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 on page 155 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 = least common multiple of p -1 and 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.