I wanted to try out how to derive p and g used in
Finite Field Diffie-Hellman.
We let J pick a prime number
for us that’s greater than 22:
] p =: x: 4 p: 22
23
In the preceding snippet, I make sure that p becomes an extended precision
number by using the extended precision verb
x:.
Let’s pick 5 as a candidate
primitive root g
modulo p and make sure that it’s extended precision as well:
] g =: x: 5
5
Now we want to derive the order of g. The order k is 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.
It’s the same as when 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}")
If you run this Python snippet, you can see the following:
Cycle length: 22
We write 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. Thus, 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 this code 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).