I wanted to briefly try out how to derive p and g used in
Finite Field Diffie-Hellman.
We let J pick a prime number
for us that is greater than 22:
] p =: x: 4 p: 22
23
Above we make sure that p becomes a extended precision number by using
x:.
Let’s pick 5 as a candidate
primitive root g
modulo p and make sure that it is extended precision as well:
] g =: x: 5
5
Now we want to derive the order of g. The order k is defined as the amount
of times that we can calculate g^n mod p until the result becomes 1:
g^1 mod p, g^2 mod p, g^3 mod p, ..., g^k mod p
If the order is p-1 for prime p, then g is a primitive root modulo p.
Or more generally, if the order is equal to the result of
Euler’s totient function
phi(p).
We also note that this cycle can never exceed phi(p). All primitive root
candidates are coprimes to p.
In (Python-like) pseudo-code, this would look like so:
import math
p = 23
g = 5
phi = sum(math.gcd(i, p) == 1 for i in range(1, p))
for i in range(1, phi + 1):
if g ** i % p == 1:
break
print(f"Cycle length: {i}")
Running the above we see
Cycle length: 22
We implement something similar in J:
order =: {{ NB. y is g, x is p
phi =. 5 p: x NB. phi is the number of coprimes
mexp =. x&|@^ NB. fast exponentiation modulo p
ix =. 1 + i. phi NB. 1, ..., p-1
mod =. y&mexp ix NB. g^1 % p, g^2 % p, ..., g^(p-1) % p
ord =. 0 i.~ ~: mod NB. find first non-unique value
ord
}}
p order g
22
The order of 5 in relation to 23 is 22. Therefore, 5 is a primitive
root usable in Finite Field Diffie-Hellman.
We can than find the order of every integer below our prime 23:
] c =: 1 + i. p - 1 NB. all integers below 23
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
c ,. p&order"0 c NB. show each number and its order
1 1
2 11
3 11
4 11
5 22
6 11
7 22
8 11
9 11
10 22
11 22
12 11
13 11
14 22
15 22
16 11
17 22
18 11
19 22
20 22
21 22
22 2
c #~ (p-1) = p&order"0 c NB. filter out all primitive roots
5 7 10 11 14 15 17 19 20 21
We wrap the above into a convenience function that returns all primitive roots for a number, even if it’s not prime.
allroots =. {{ NB. y is the number we investigate
cop =. I. 1 = y +. i. y NB. determine all coprimes
phi =. # cop NB. phi(y)
mexp =. y&|@^ NB. fast exponentiation modulo y
exps =. cop mexp/ 1 + i. phi NB. calculate cycles for all coprimes
orders =. 0 i.~"1 ~:"1 exps NB. get cycle length
roots =. orders = phi NB. find primitive roots modulo y
roots # cop
}}
allroots p
5 7 10 11 14 15 17 19 20 21
allroots 1
0
Let’s aim high and replicate the table from the Wikipedia article on primitive roots:
NB. show number n, primitive roots and phi(n)
> ('n';'primitive roots mod n';'phi(n)');(];allroots;5&p:) L:0 |: ;/ 1 + i. 31
We get the following answer:
┌──┬────────────────────────────────┬──────┐
│n │primitive roots mod n │phi(n)│
├──┼────────────────────────────────┼──────┤
│1 │0 │1 │
├──┼────────────────────────────────┼──────┤
│2 │1 │1 │
├──┼────────────────────────────────┼──────┤
│3 │2 │2 │
├──┼────────────────────────────────┼──────┤
│4 │3 │2 │
├──┼────────────────────────────────┼──────┤
│5 │2 3 │4 │
├──┼────────────────────────────────┼──────┤
│6 │5 │2 │
├──┼────────────────────────────────┼──────┤
│7 │3 5 │6 │
├──┼────────────────────────────────┼──────┤
│8 │ │4 │
├──┼────────────────────────────────┼──────┤
│9 │2 5 │6 │
├──┼────────────────────────────────┼──────┤
│10│3 7 │4 │
├──┼────────────────────────────────┼──────┤
│11│2 6 7 8 │10 │
├──┼────────────────────────────────┼──────┤
│12│ │4 │
├──┼────────────────────────────────┼──────┤
│13│2 6 7 11 │12 │
├──┼────────────────────────────────┼──────┤
│14│3 5 │6 │
├──┼────────────────────────────────┼──────┤
│15│ │8 │
├──┼────────────────────────────────┼──────┤
│16│ │8 │
├──┼────────────────────────────────┼──────┤
│17│3 5 6 7 10 11 12 14 │16 │
├──┼────────────────────────────────┼──────┤
│18│5 11 │6 │
├──┼────────────────────────────────┼──────┤
│19│2 3 10 13 14 15 │18 │
├──┼────────────────────────────────┼──────┤
│20│ │8 │
├──┼────────────────────────────────┼──────┤
│21│ │12 │
├──┼────────────────────────────────┼──────┤
│22│7 13 17 19 │10 │
├──┼────────────────────────────────┼──────┤
│23│5 7 10 11 14 15 17 19 20 21 │22 │
├──┼────────────────────────────────┼──────┤
│24│ │8 │
├──┼────────────────────────────────┼──────┤
│25│2 3 8 12 13 17 22 23 │20 │
├──┼────────────────────────────────┼──────┤
│26│7 11 15 19 │12 │
├──┼────────────────────────────────┼──────┤
│27│2 5 11 14 20 23 │18 │
├──┼────────────────────────────────┼──────┤
│28│ │12 │
├──┼────────────────────────────────┼──────┤
│29│2 3 8 10 11 14 15 18 19 21 26 27│28 │
├──┼────────────────────────────────┼──────┤
│30│ │8 │
├──┼────────────────────────────────┼──────┤
│31│3 11 12 13 17 21 22 24 │30 │
└──┴────────────────────────────────┴──────┘
The first column is n, the second column shows the primitive roots modulo n
and the third column shows phi(n).