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).
 
Source
< Prev   CONTENTS   Source   Next >