Primitive root 𝑚𝑜𝑑 𝑝
A primitive root 𝑚𝑜𝑑 𝑛 is a value 1 ≤ 𝑎 ≤ 𝑛 − 1 such that the
series 𝑎, 𝑎2, 𝑎3, … , 𝑎𝑛−1 is a permutation of all of the values between 1 and 𝑛 − 1.
As the book demonstrates, 2 is a primitive root 𝑚𝑜𝑑 13 but 3 is not. Here are the values of 2𝑖 𝑚𝑜𝑑 13 for 𝑖 = 0. .12:
1,2,4,8,3,6,12,11,9,5,10,7 The values of 3𝑖 𝑚𝑜𝑑 13 for 𝑖 = 0..12 are:
1,3,9,1,3,9,1,3,9,1,3,9
Essentially, a number is primitive 𝑚𝑜𝑑 𝑛 if the sequence of its
powers from 0 to 𝑝 − 1 doesn’t return to 1. In DHKE, 𝑛 is a prime and we’ll now call it 𝑝.
How does one determine whether a value 𝑎 is
primitive 𝑚𝑜𝑑 𝑝? We can use the following algorithm. But first, let’s go to page 57 in the book to define Euler’s totient function 𝜙.
Given a value 1 ≤ 𝑎 ≤ 𝑝 − 1:
1. Compute 𝜙(𝑝) = 𝑝 − 1. This is true because every value
from 1 to 𝑝 − 1 is relatively prime to 𝑝.
2. Factor 𝜙(𝑝) into powers of its prime factors.
Assume𝜙(𝑝)=𝑞𝑒0 ⋅𝑞𝑒1 ⋯𝑞𝑒𝑘. 01𝑘
3. For each value in the list 𝑞0, 𝑞1, … , 𝑞𝑘
calculate 𝑎𝜙(𝑝)⁄𝑞𝑖 (𝑚𝑜𝑑 𝑝). If the value is 1, return false.
4. Return true.
In step 3, we’re looking for a power less than 𝑝 − 1 that gets us back to 1. Because that power is less than 𝑝 − 1, 𝑎 is not primitive.
This algorithm isn’t very fast. The size of the input is the number of bits in 𝑝, which is lg(𝑝). Assuming that the generalized Riemann hypothesis is true, the above runs in time 𝑂(lg(𝑝)6). This is sextic polynomial time.