Primitive roots and Diffie-Hellman key exchange

The Diffie-Hellman key exchange algorithm starts with the selection of a prime number plus one of its primitive roots (sometimes called "primitive generators"). So, what's a primitive root?

If the prime number is p, a primitive root (or generator) g is a number, that
 when n goes from 1 to p-1,
 then gⁿ mod p goes through all the numbers 1...(p-1) in some order.

gⁿ mod p means the remainder when you raise g to n and divide by p.

An example is worth a thousand words. If 5 is the prime number, let's show that 3 is one of its primitive roots (there can be many), but 4 is not.

3 is a primitive root of 5:

We take all the integers starting with 1, right up to one less than 5, in the first column. Then we raise our candidate root 3 to each number, generating the sequence of powers of the candidate root in the second column. We divide that result by our prime, 5, and record the remainder (that's what 3ⁿ mod 5 means). If the set of remainders in the third column reproduces the set of integers in the first (the order need not be identical), then 3 is a primitive root of 5. It looks like 3 is indeed a primitive root of 5. 4 on the other hand is not, because we won't get the values 1 through 4 when we repeat the above process.

4 is not a primitive root of 5:

The set of integers in the third column is not the same as the set of integers in the first column. So 4 is not a prime root of 5.

To help do problems like this you can download an use an Excel spreadsheet that codifies the above procedure. I suggest you do 2 or 3 of them by hand as well, to make sure you get the idea.

The Diffie-Hellman key exchange algorithm is explained on pages 96-97 of the textbook (Yuan/Strayer). In it, the two parties select and exchange a prime number and one of its primitive roots. They also each select (but do not exchange) some random integer. From those ingredients the algorithm lets them  independently calculate the same key value. Study the explanation in the book to understand the steps of the algorithm.

Assignment:

Answer the following 7 questions. Please submit answers to them onto the remote Unix machine using these preparation and submittal instructions. Name your file "roots". You could prepare your text file on sputnik itself using an editor like vi. You may not know how to use vi. You could then prepare your file in Windows using Notepad and, when finished, use ftp to connect to sputnik (log in with the same username and password as you do for telnet). Then navigate to the "assignments" subdirectory and then transmit your file.

1. Is 2 a primitive root of 3?
  a. yes
  b. no

2. Is 2 a primitive root of 5?
  a. yes
  b. no

3. Is 3 a primitive root of 7?
  a. yes
  b. no

4. Is 3 a primitive root of 11?
  a. yes
  b. no

5. Is 5 a primitive root of 7?
  a. yes
  b. no

6. Is 5 a primitive root of 11?
  a. yes
  b. no

7. 8 is a primitive root of 11. If these numbers are used by two parties in a Diffie-Hellman key exchange (i.e., g=8 p=11) where the random integer chosen by the first party (Initiator) is 5 and the random integer chosen by the second party (Responder) is 7, what is the value of the key that they will both end up calculating?
  a. 1
  b. 2
  c. 3
  d. 4
  e. 5
  f. 6
  g. 7
  h. 8
  i. 9
  j. 10
  k. 11