Take a cyclic group Z_n with the order n. The elements are:
Z_n = {1,2,...,n-1}
For each of the elements, let us call them a, you test if a^x % n gives us all numbers in Z_n; x is here all numbers from 1 to n-1. If the element does generator our entire group, it is a generator.
I need a program that gets the order of the group and gives back all the generators. Here is what I tried:
import math
active = True
def test(a,b):
a.sort()
b.sort()
return a == b
while active:
order = input("Order of the cyclic group: ")
print
group = []
for i in range(1, order):
group.append(i)
res = []
for x in group:
foo = []
foo.append(x)
for y in group:
foo.append((x**y) % order)
if(test(group,foo)):
res.append(res,foo,axis=0)
print res
Sadly, it gives back an empty list.
One change you can make is to use sets instead of lists to store the results, which makes comparing them easier.
def generators(n):
s = set(range(1, n))
results = []
for a in s:
g = set()
for x in s:
g.add((a**x) % n)
if g == s:
results.append(a)
return results
for i in range(100):
gens = generators(i)
if gens:
print(f"Z_{i} has generators {gens}")
Prints
Z_2 has generators [1]
Z_3 has generators [2]
Z_5 has generators [2, 3]
Z_7 has generators [3, 5]
Z_11 has generators [2, 6, 7, 8]
Z_13 has generators [2, 6, 7, 11]
Z_17 has generators [3, 5, 6, 7, 10, 11, 12, 14]
Z_19 has generators [2, 3, 10, 13, 14, 15]
Z_23 has generators [5, 7, 10, 11, 14, 15, 17, 19, 20, 21]
Z_29 has generators [2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27]
Z_31 has generators [3, 11, 12, 13, 17, 21, 22, 24]
Z_37 has generators [2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35]
Z_41 has generators [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35]
Z_43 has generators [3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34]
Z_47 has generators [5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45]
Z_53 has generators [2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51]
Z_59 has generators [2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 56]
Z_61 has generators [2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59]
Z_67 has generators [2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63]
Z_71 has generators [7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69]
Z_73 has generators [5, 11, 13, 14, 15, 20, 26, 28, 29, 31, 33, 34, 39, 40, 42, 44, 45, 47, 53, 58, 59, 60, 62, 68]
Z_79 has generators [3, 6, 7, 28, 29, 30, 34, 35, 37, 39, 43, 47, 48, 53, 54, 59, 60, 63, 66, 68, 70, 74, 75, 77]
Z_83 has generators [2, 5, 6, 8, 13, 14, 15, 18, 19, 20, 22, 24, 32, 34, 35, 39, 42, 43, 45, 46, 47, 50, 52, 53, 54, 55, 56, 57, 58, 60, 62, 66, 67, 71, 72, 73, 74, 76, 79, 80]
Z_89 has generators [3, 6, 7, 13, 14, 15, 19, 23, 24, 26, 27, 28, 29, 30, 31, 33, 35, 38, 41, 43, 46, 48, 51, 54, 56, 58, 59, 60, 61, 62, 63, 65, 66, 70, 74, 75, 76, 82, 83, 86]
Z_97 has generators [5, 7, 10, 13, 14, 15, 17, 21, 23, 26, 29, 37, 38, 39, 40, 41, 56, 57, 58, 59, 60, 68, 71, 74, 76, 80, 82, 83, 84, 87, 90, 92]