Generators and elements of high order
Recall (Definition 2.169) that if G is a (multiplicative) finite group, the order of an element a e G is the least positive integer t such that а^{1} = 1. If there are n elements in G, and if a e G is an element of order n, then G is said to be cyclic and a is called a generator or a primitive element of G (Definition 2.167). Of special interest for cryptographic applications are the multiplicative group Z* of the integers modulo a prime p, and the multiplicative group Fjm of the finite field F_{2}™ of characteristic two; these groups are cyclic (Fact 2.213). Also of interest is the group Z* (Definition 2.124), where n is the product of two distinct odd primes. This section deals with the problem of finding generators and other elements of high order in Z*, , and Z*. See §2.5.1 for background in group theory and §2.6 for
background in finite fields.
Algorithm 4.79 is an efficient method for determining the order of a group element, given the prime factorization of the group order n. The correctness of the algorithm follows from the fact that the order of an element must divide n (Fact 2.171).
m |
к or (к1,к2,кз) |
m |
к or (к1,к2,кз) |
m |
к or (fel,/C2,/C3) |
m |
к or (fcl,fc-2,fc3) |
2 |
1 |
59 |
22,21, 1 |
не |
71, 70, 1 |
173 |
100, 99,1 |
3 |
1 |
60 |
1 |
117 |
20, 18, 2 |
174 |
13 |
4 |
1 |
61 |
16, 15, 1 |
118 |
33 |
175 |
6 |
5 |
2 |
62 |
57, 56, 1 |
119 |
8 |
176 |
119,118, 1 |
6 |
1 |
63 |
1 |
120 |
118, 111,7 |
177 |
8 |
7 |
1 |
64 |
4,3, 1 |
121 |
18 |
178 |
87 |
8 |
6,5, 1 |
65 |
18 |
122 |
60, 59, 1 |
179 |
34, 33, 1 |
9 |
4 |
66 |
10, 9, 1 |
123 |
2 |
180 |
37, 36, 1 |
10 |
3 |
67 |
10, 9, 1 |
124 |
37 |
181 |
7,6, 1 |
11 |
2 |
68 |
9 |
125 |
108, 107, 1 |
182 |
128, 127,1 |
12 |
7,4, 3 |
69 |
29, 27, 2 |
126 |
37, 36, 1 |
183 |
56 |
13 |
4, 3, 1 |
70 |
16, 15, 1 |
127 |
1 |
184 |
102, 101, 1 |
14 |
12, 11, 1 |
71 |
6 |
128 |
29, 27, 2 |
185 |
24 |
15 |
1 |
72 |
53, 47, 6 |
129 |
5 |
186 |
23, 22, 1 |
16 |
5,3,2 |
73 |
25 |
130 |
3 |
187 |
58, 57, 1 |
17 |
3 |
74 |
16, 15, 1 |
131 |
48, 47, 1 |
188 |
74, 73, 1 |
18 |
7 |
75 |
11, 10, 1 |
132 |
29 |
189 |
127, 126, 1 |
19 |
6,5, 1 |
76 |
36, 35, 1 |
133 |
52,51, 1 |
190 |
18, 17, 1 |
20 |
3 |
77 |
31, 30, 1 |
134 |
57 |
191 |
9 |
21 |
2 |
78 |
20, 19, 1 |
135 |
11 |
192 |
28, 27, 1 |
22 |
1 |
79 |
9 |
136 |
126, 125, 1 |
193 |
15 |
23 |
5 |
80 |
38, 37, 1 |
137 |
21 |
194 |
87 |
24 |
4, 3, 1 |
81 |
4 |
138 |
8,7, 1 |
195 |
10, 9, 1 |
25 |
3 |
82 |
38, 35, 3 |
139 |
8,5,3 |
196 |
66, 65, 1 |
26 |
8,7, 1 |
83 |
46, 45, 1 |
140 |
29 |
197 |
62,61, 1 |
27 |
8,7, 1 |
84 |
13 |
141 |
32,31, 1 |
198 |
65 |
28 |
3 |
85 |
28,27, 1 |
142 |
21 |
199 |
34 |
29 |
2 |
86 |
13, 12, 1 |
143 |
21, 20, 1 |
200 |
42,41, 1 |
30 |
16, 15, 1 |
87 |
13 |
144 |
70, 69, 1 |
201 |
14 |
31 |
3 |
88 |
72,71, 1 |
145 |
52 |
202 |
55 |
32 |
28, 27, 1 |
89 |
38 |
146 |
60, 59, 1 |
203 |
8,7, 1 |
33 |
13 |
90 |
19, 18, 1 |
147 |
38, 37, 1 |
204 |
74, 73, 1 |
34 |
15, 14, 1 |
91 |
84, 83, 1 |
148 |
27 |
205 |
30, 29, 1 |
35 |
2 |
92 |
13, 12, 1 |
149 |
110, 109,1 |
206 |
29, 28, 1 |
36 |
11 |
93 |
2 |
150 |
53 |
207 |
43 |
37 |
12, 10, 2 |
94 |
21 |
151 |
3 |
208 |
62, 59, 3 |
38 |
6,5, 1 |
95 |
11 |
152 |
66, 65, 1 |
209 |
6 |
39 |
4 |
96 |
49, 47, 2 |
153 |
1 |
210 |
35, 32, 3 |
40 |
21, 19,2 |
97 |
6 |
154 |
129, 127,2 |
211 |
46,45, 1 |
41 |
3 |
98 |
11 |
155 |
32,31, 1 |
212 |
105 |
42 |
23, 22, 1 |
99 |
47, 45, 2 |
156 |
116, 115, 1 |
213 |
8,7, 1 |
43 |
6,5, 1 |
100 |
37 |
157 |
27, 26, 1 |
214 |
49, 48, 1 |
44 |
27, 26, 1 |
101 |
7,6, 1 |
158 |
27, 26, 1 |
215 |
23 |
45 |
4, 3, 1 |
102 |
77, 76, 1 |
159 |
31 |
216 |
196, 195, 1 |
46 |
21,20, 1 |
103 |
9 |
160 |
19, 18, 1 |
217 |
45 |
47 |
5 |
104 |
11, 10, 1 |
161 |
18 |
218 |
11 |
48 |
28, 27, 1 |
105 |
16 |
162 |
88, 87, 1 |
219 |
19, 18, 1 |
49 |
9 |
106 |
15 |
163 |
60, 59, 1 |
220 |
15, 14, 1 |
50 |
27, 26, 1 |
107 |
65, 63, 2 |
164 |
14, 13, 1 |
221 |
35, 34, 1 |
51 |
16, 15, 1 |
108 |
31 |
165 |
31, 30, 1 |
222 |
92,91, 1 |
52 |
3 |
109 |
7,6, 1 |
166 |
39, 38, 1 |
223 |
33 |
53 |
16, 15, 1 |
110 |
13, 12, 1 |
167 |
6 |
224 |
31,30, 1 |
54 |
37, 36, 1 |
111 |
10 |
168 |
17, 15,2 |
225 |
32 |
55 |
24 |
112 |
45, 43, 2 |
169 |
34 |
226 |
58, 57, 1 |
56 |
22,21, 1 |
113 |
9 |
170 |
23 |
227 |
46,45, 1 |
57 |
7 |
114 |
82, 81, 1 |
171 |
19, 18, 1 |
228 |
148, 147, 1 |
58 |
19 |
115 |
15, 14, 1 |
172 |
7 |
229 |
64, 63, 1 |
Table 4.8: Primitive polynomials over Z2. For each m, 1 < m < 229, an exponent к is given for which the trinomial x^{m}+x^{k} +1 is primitive over Z2. If no such trinomial exists, a triple of exponents (ki,k2, кз) is given for which the pentanomial x^{m} + x^{k}' + x^{k}'^{2} + х^{кз} + 1 is primitive over Z2.
j |
m |
к (k_{u}k2,k_{3}) |
1 |
2 |
1 |
2 |
3 |
1 |
3 |
5 |
2 |
4 |
7 |
1,3 |
5 |
13 |
none (4,3,1) |
6 |
17 |
3,5,6 |
7 |
19 |
none (5,2,1) |
8 |
31 |
3, 6, 7,13 |
9 |
61 |
none (43,26,14) |
10 |
89 |
38 |
11 |
107 |
none (82,57,31) |
12 |
127 |
1,7,15,30, 63 |
13 |
521 |
32,48,158,168 |
14 |
607 |
105, 147,273 |
15 |
1279 |
216,418 |
16 |
2203 |
none (1656,1197,585) |
17 |
2281 |
715, 915,1029 |
18 |
3217 |
67, 576 |
19 |
4253 |
none (3297,2254,1093) |
20 |
4423 |
271, 369, 370, 649,1393, 1419, 2098 |
21 |
9689 |
84,471,1836, 2444,4187 |
22 |
9941 |
none (7449,4964,2475) |
23 |
11213 |
none (8218,6181,2304) |
24 |
19937 |
881,7083,9842 |
25 |
21701 |
none (15986,11393,5073) |
26 |
23209 |
1530, 6619,9739 |
27 |
44497 |
8575, 21034 |
Table 4.9: Primitive polynomials of degree m over Z2,2™ — 1 a Mersenne prime. For each exponent m = Mj of the first 27 Mersenne primes, the table lists all values of к, 1 < к < m/2, for which the trinomial x^{m} + x^{k} + 1 is irreducible over Z 2. If no such trinomial exists, a triple of exponents (A'i, A'2. ks) is listed such that the pentanomial x^{m} + x^{kl} + x^{k}'^{2} + x^{k} ' + 1 is irreducible over Z2.
4.79 Algorithm Determining the order of a group element
INPUT: a (multiplicative) finite group G of order n, an element a e G, and the prime factorization n = pi^{1} рф ■ ■ -p^{e}k^{k}.
OUTPUT: the order t of a.
- 1. Set t^n.
- 2. For i from 1 to к do the following:
- 2.1 Set U-t/p^.
- 2.2 Compute ai'S-a*.
- 2.3 While 01 ф 1 do the following: compute ai<-af and set U-t ■ p_{t}.
- 3. Retum(f).
Suppose now that G is a cyclic group of order n. Then for any divisor d of n the number of elements of order d in G is exactly
4.80 Algorithm Finding a generator of a cyclic group
INPUT: a cyclic group G of order n, and the prime factorization n = Py'p'f • • -р%^{к} ■ OUTPUT: a generator a of G.
- 1. Choose a random element a in G.
- 2. For i from 1 to к do the following:
- 2.1 Compute b-^a^{n}/^{pi}.
- 2.2 If 6 = 1 then go to step 1.
- 3. Retum(a).
- 4.81 Note (group elements of high order) In some situations it may be desirable to have an element of high order, and not a generator. Given a generator a in a cychc group G of order n, and given a divisor d of n, an element /3 of order d in G can be efficiently obtained as follows: 0 = a^{n}/^{d}. If q is a prime divisor of the order n of a cyclic group G, then the following method finds an element 3 e G of order q without first having to find a generator of G: select a random element д € G and compute 0 = g^{n}!^{q} repeat until в Ф 1.
- 4.82 Note (generators of F^m) There are two basic approaches to finding a generator of F^m. Both techniques require the factorization of the order of F^m, namely 2^{m} - 1.
- (i) Generate a monic primitive polynomial f(x) of degree m over Z_{2} (Algorithm 4.78). The finite field F_{2}m can then be represented as Z_{2}[x]/(/(a;)), the set of all polynomials over Z_{2} modulo f{x), and the element a = x is a generator.
- (ii) Select the method for representing elements of F_{2}"< first. Then use Algorithm 4.80 with G = F^m and n = 2^{m} — 1 to find a generator a of F^..».
If n = pq, where p and q are distinct odd primes, then Z* is a non-cyclic group of order ф(п) = (p - l)(q - 1). The maximum order of an element in Z* is lcm(p — 1, q — 1). Algorithm 4.83 is a method for generating such an element which requires the factorizations of p — 1 and q — 1.
4.83 Algorithm Selecting an element of maximum order in Z„, where n = pq
INPUT: two distinct odd primes, p, q, and the factorizations of p - 1 and q — 1.
OUTPUT: an element a of maximum order lcm(p — 1, q — 1) in Z*, where n = pq.
- 1. Use Algorithm 4.80 with G = Z* and n = p — 1 to find a generator a of Z*.
- 2. Use Algorithm 4.80 with G = Z* and n = q — 1 to find a generator b of Z*.
- 3. Use Gauss’s algorithm (Algorithm 2.121) to find an integer a, 1 < a < n - 1, satisfying a = a (mod p) and a = b (mod q).
- 4. Retum(a).