Question

1. 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.

Answer 1

1.

a)

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

b)

A primitive root modulo 7 would have order 6, but $2^3=8≡1(mod7)$ ,

so 2 is not a primitive root modulo 7.

3.

a)

$2x^2-5x+1=0$

$x=\frac{5\pm\sqrt{25-8}}{4}=\frac{5\pm\sqrt{17}}{4}$

$x_1=0.22,x_2=5.15$

$f(x)=2(x-0.22)(x-5.15)$

$f(0)>0$ for $x<0.22$ and $x>5.15$

smallest value of n > 0 for which f(n) > 0 :

$n=6$

b)

for n=6:

$f(6)=43>0$

for n=k let:

$2k^2-5k+1>0$

then for n=k+1:

$2(k+1)^2-5(k+1)+1=2k^2-5k+1+4k-3>0$

since $2k^2-5k+1>0$ , and $4k-3>0$ for $k>6$

4.

input:

b

int k

f(0)=b

output:

f(k+1)=3*f(k)

1.

c)

Alice and Bob agree to use the prime p = 7 and the primitive root g = 3. Alice chooses the secret key k₁ = 5 and computes

$A=5\equiv 3^5(mod\ 7)$

Bob chooses the secret key k₂ = 4 and computes

$B=4\equiv 3^4(mod\ 7)$

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 k₁ = 5 and k₂ = 4 are not transmitted and remain secret. Then Alice and Bob are both able to compute the number

$3^{k_1\cdot k_2}\equiv A^{k_2}\equiv B^{k_1}(mod\ 7)$

$2\equiv3^{5\cdot 4}\equiv 5^{4}\equiv 4^{5}(mod\ 7)$

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 

$3^{k_1}\equiv 5(mod\ 7)$ or $3^{k_2}\equiv 4(mod\ 7)$

since then she will know one of their secret exponents.