6.4 Suppose that p is an odd prime and k is a positive integer. The multiplicative...

 

Transcribed Image Text:

6.4 Suppose that p is an odd prime and k is a positive integer. The multiplicative group Zpk has order p-1 (p - 1), and is known to be cyclic. A generator for this group is called a primitive element modulo p*. (a) Suppose that a is a primitive element modulo p. Prove that at least one of a or a + p is a primitive element modulo p. (b) Describe how to efficiently verify that 3 is a primitive root modulo 29 and modulo 292. Note: It can be shown that if a is a primitive root modulo p and modulo p, then it is a primitive root modulo p* for all positive integers k (you do not have to prove this fact). Therefore, it follows that 3 is a primitive root modulo 29* for all positive integers k. (c) Find an integer a that is a primitive root modulo 29 but not a primitive root modulo 29. (d) Use the POHLIG-HELLMAN ALGORITHM to compute the discrete logarithm of 3344 to the base 3 in the multiplicative group Z24389. 6.4 Suppose that p is an odd prime and k is a positive integer. The multiplicative group Zpk has order p-1 (p - 1), and is known to be cyclic. A generator for this group is called a primitive element modulo p*. (a) Suppose that a is a primitive element modulo p. Prove that at least one of a or a + p is a primitive element modulo p. (b) Describe how to efficiently verify that 3 is a primitive root modulo 29 and modulo 292. Note: It can be shown that if a is a primitive root modulo p and modulo p, then it is a primitive root modulo p* for all positive integers k (you do not have to prove this fact). Therefore, it follows that 3 is a primitive root modulo 29* for all positive integers k. (c) Find an integer a that is a primitive root modulo 29 but not a primitive root modulo 29. (d) Use the POHLIG-HELLMAN ALGORITHM to compute the discrete logarithm of 3344 to the base 3 in the multiplicative group Z24389.