Program to find generators of a cyclic group
Write a C/C++ program to find generators of a cyclic group.
A cyclic group is a group that is generated by a single element. That means that there exists an element g, say, such that every other element of the group can be written as a power of g. This element g is the generator of the group. For example,
Input: G=<Z6,+>
Output:
A group is a cyclic group with 2 generators.
g1 = 1 g2 = 5
Input: G=<Z18,+>
Output:
A group is a cyclic group with 6 generators.
g1 = 1 g2 = 5 g3 = 7 g4 = 11 g5 = 13 g6 = 17
Implementation:
Following is the code to find the generators of a cyclic group in C:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include <stdio.h> #include <stdlib.h> #include <math.h> int gcd(int a, int b) { int q, r; while (b > 0) { q = a / b; r = a - q * b; a = b; b = r; } return a; } // C program to find generators of a cyclic group int main() { char ch, op; int a, k; int mode = 0; int val; int ord[50], g[50], H[50]; bool cyclic = false; int elements[100]; int order; while (!feof(stdin)) { fscanf(stdin, "G=<Z%d\n", &a); ch = getc(stdin); if (ch == '*') { mode = 1; } else { ungetc(ch, stdin); } fscanf(stdin, ",%c>\n", &op); if (mode) { printf("G=<Z%d*,%c>\n", a, op); k = 0; for (int i = 0; i < a; i++) { if (gcd(a, i) == 1) { // co-prime elements[k++] = i; } } elements[k] = '\0'; mode = 0; } else { printf("G=<Z%d,%c>\n", a, op); for (int i = 0; i < a; i++) { elements[i] = i; } k = a; } printf("G = {"); for (int i = 0; i < k; i++) { printf("%d", elements[i]); (i < k-1) ? printf(",") : printf("}"); } order = k; printf("\nThe order of the group is %d.\n\n", order); for (int i = 0; i < k; i++) { int temp = 1; while (1) { if (op == '+') { val = elements[i] * temp; if (val % a == 0) { ord[i] = temp; printf("order(%d) = %d\n", elements[i], temp); break; } } else if (op == '*') { val = int(pow(elements[i], temp)); if (val % a == 1) { ord[i] = temp; printf("order(%d) = %d\n", elements[i], temp); break; } } temp++; } } int x = 0, count = 0; for (int i = 0; i < k; i++) { if (ord[i] == order) { g[x++] = elements[i]; cyclic = true; count++; } } if (cyclic) { printf("A group is a cyclic group with %d generators", count); for (int i = 0; i < count; i++) { printf("g%d = %d ", i + 1, g[i]); } } else { printf("The group is not a cyclic group.\n"); } printf("\n\n——————————————————————————————————————————————\n\n"); } return 0; } |
Input:
G=<Z6,+>
G=<Z18,+>
G=<Z8,+>
G=<Z7*,*>
G=<Z18*,*>
Output:
G=<Z6,+>
G = {0,1,2,3,4,5}
The order of the group is 6.
order(0) = 1
order(1) = 6
order(2) = 3
order(3) = 2
order(4) = 3
order(5) = 6
A group is a cyclic group with 2 generators.
g1 = 1 g2 = 5
——————————————————————————————————————————————
G=<Z18,+>
G = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}
The order of the group is 18.
order(0) = 1
order(1) = 18
order(2) = 9
order(3) = 6
order(4) = 9
order(5) = 18
order(6) = 3
order(7) = 18
order(8) = 9
order(9) = 2
order(10) = 9
order(11) = 18
order(12) = 3
order(13) = 18
order(14) = 9
order(15) = 6
order(16) = 9
order(17) = 18
A group is a cyclic group with 6 generators.
g1 = 1 g2 = 5 g3 = 7 g4 = 11 g5 = 13 g6 = 17
——————————————————————————————————————————————
G=<Z8,+>
G = {0,1,2,3,4,5,6,7}
The order of the group is 8.
order(0) = 1
order(1) = 8
order(2) = 4
order(3) = 8
order(4) = 2
order(5) = 8
order(6) = 4
order(7) = 8
A group is a cyclic group with 4 generators.
g1 = 1 g2 = 3 g3 = 5 g4 = 7
——————————————————————————————————————————————
G=<Z7*,*>
G = {1,2,3,4,5,6}
The order of the group is 6.
order(1) = 1
order(2) = 3
order(3) = 6
order(4) = 3
order(5) = 6
order(6) = 2
A group is a cyclic group with 2 generators.
g1 = 3 g2 = 5
——————————————————————————————————————————————
G=<Z18*,*>
G = {1,5,7,11,13,17}
The order of the group is 6.
order(1) = 1
order(5) = 6
order(7) = 3
order(11) = 6
order(13) = 3
order(17) = 2
A group is a cyclic group with 2 generators.
g1 = 5 g2 = 11
That’s all about finding generators of a cyclic group.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)