a) Show or verify that 3 is a primitive root of the prime p=7. b) Show that 2 is not a primitive root of 7. c) Show the steps of the Diffie-Hellman key agreement protocol between Alice and Bob, assuming they use the prime 7 and its primitive root 3, and Alice’s secret integer is k1=5 and Bob’s secret integer is k2=4. 3 Consider the function f(n) = 2n2-5n+1. a) What is the smallest value of n for which f(n)0 ? b) Use mathematical induction to prove that f(n)0 for all n the value in part a). 4 Write the pseudocode for a recursive algorithm to compute b3k, where b is a real number and k is a positive integer. Use the fact that b3k+1=(b3k)3.
The Answer to the Question
is below this banner.
Here's the Solution to this Question
If p is prime, then b is a primitive root for p if the powers of b include all of the residue classes mod p
Since we achieved all values from 1 to 6 in our residue results, then 3 is a primitive root of 7
A primitive root modulo 7 would have order 6, but ,
so 2 is not a primitive root modulo 7.
smallest value of n > 0 for which f(n) > 0 :
for n=k let:
then for n=k+1:
since , and for
Alice and Bob agree to use the prime p = 7 and the primitive root g = 3. Alice chooses the secret key k1 = 5 and computes
Bob chooses the secret key k2 = 4 and computes
Alice sends Bob the number 5 and Bob sends Alice the number 4. Both of these transmissions are done over an insecure channel, so both A = 5 and B = 4 should be considered public knowledge. The numbers k1 = 5 and k2 = 4 are not transmitted and remain secret. Then Alice and Bob are both able to compute the number
so 2 is their shared secret.
Suppose that Eve sees this entire exchange. She can reconstitute Alice’s and Bob’s shared secret if she can solve either of the congruences
since then she will know one of their secret exponents.