# 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 F2™ 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 xm+xk +1 is primitive over Z2. If no such trinomial exists, a triple of exponents (ki,k2, кз) is given for which the pentanomial xm + xk' + xk'2 + хкз + 1 is primitive over Z2.

 j m к (kuk2,k3) 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 xm + xk + 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 xm + xkl + xk'2 + xk ' + 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 = pi1 рф ■ ■ -pekk.

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 ■ pt.
• 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 (d) (Fact 2.173(h)), where 0 is the Euler phi function (Definition 2.100). In particular, G has exactly ф(п) generators, and hence the probability of a random element in G being a generator is ф(п)/п. Using the lower bound for the Euler phi function (Fact 2.102), this probability can be seen to be at least 1/(6 In In n). This suggests the following efficient randomized algorithm for finding a generator of a cyclic group.

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-^an/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 = an/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 = gn!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 2m - 1.
• (i) Generate a monic primitive polynomial f(x) of degree m over Z2 (Algorithm 4.78). The finite field F2m can then be represented as Z2[x]/(/(a;)), the set of all polynomials over Z2 modulo f{x), and the element a = x is a generator.
• (ii) Select the method for representing elements of F2"< first. Then use Algorithm 4.80 with G = F^m and n = 2m — 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).