-
Notifications
You must be signed in to change notification settings - Fork 21
/
Copy pathIrreduciblePolynomial.cs
385 lines (370 loc) · 36.5 KB
/
IrreduciblePolynomial.cs
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
using System;
using System.Numerics;
using Moserware.Numerics;
namespace Moserware.Algebra {
/// <summary>
/// Polynomials that are irreducible (for use with a finite field).
/// </summary>
public class IrreduciblePolynomial {
private const int InnerTermsPerPolynomial = 3;
// pentanomials
// For details on where this came from, see my question on:
// http://math.stackexchange.com/questions/14787/finding-irreducible-polynomials-over-gf2-with-the-fewest-terms
// The larger ones came directly from "Table of Low-Weight Binary Irreducible Polynomials" by HP Research
private static readonly int[] _TermPowers = new[] {
4, 3, 1, 5, 3, 1, 4, 3, 1, 7, 3, 2, 5, 4, 3, 5, 3, 2, 7, 4
, 2, 4, 3, 1, // x^64
10, 9, 3, 9, 4, 2, 7, 6, 2, 10, 9, 6, 4, 3, 1, 5, 4, 3, 4,
3, 1, 7, 2, 1, // x^128
5, 3, 2, 7, 4, 2, 6, 3, 2, 5, 3, 2, 15, 3, 2, 11, 3, 2, 9,
8, 7, 7, 2, 1, // x^192
5, 3, 2, 9, 3, 1, 7, 3, 1, 9, 8, 3, 9, 4, 2, 8, 5, 3, 15,
14, 10, 10, 5, 2, // x^256
9, 6, 2, 9, 3, 2, 9, 5, 2, 11, 10, 1, 7, 3, 2, 11, 2, 1, 9
, 7, 4, 4, 3, 1, // x^320
8, 3, 1, 7, 4, 1, 7, 2, 1, 13, 11, 6, 5, 3, 2, 7, 3, 2, 8,
7, 5, 12, 3, 2, // x^384
13, 10, 6, 5, 3, 2, 5, 3, 2, 9, 5, 2, 9, 7, 2, 13, 4, 3, 4
, 3, 1, 11, 6, 4, // x^448
18, 9, 6, 19, 18, 13, 11, 3, 2, 15, 9, 6, 4, 3, 1, 16, 5,
2, 15, 14, 6, 8, 5, 2, // x^512
15, 11, 2, 11, 6, 2, 7, 5, 3, 8, 3, 1, 19, 16, 9, 11, 9, 6
, 15, 7, 6, 13, 4, 3, // x^576
14, 13, 3, 13, 6, 3, 9, 5, 2, 19, 13, 6, 19, 10, 3, 11, 6,
5, 9, 2, 1, 14, 3, 2, // x^640
13, 3, 1, 7, 5, 4, 11, 9, 8, 11, 6, 5, 23, 16, 9, 19, 14,
6, 23, 10, 2, 8, 3, 2, // x^704
5, 4, 3, 9, 6, 4, 4, 3, 2, 13, 8, 6, 13, 11, 1, 13, 10, 3,
11, 6, 5, 19, 17, 4, // x^768
15, 14, 7, 13, 9, 6, 9, 7, 3, 9, 7, 1, 14, 3, 2, 11, 8, 2,
11, 6, 4, 13, 5, 2, // x^832
11, 5, 1, 11, 4, 1, 19, 10, 3, 21, 10, 6, 13, 3, 1, 15, 7,
5, 19, 18, 10, 7, 5, 3, // x^896
12, 7, 2, 7, 5, 1, 14, 9, 6, 10, 3, 2, 15, 13, 12, 12, 11,
9, 16, 9, 7, 12, 9, 3, // x^960
9, 5, 2, 17, 10, 6, 24, 9, 3, 17, 15, 13, 5, 4, 3, 19, 17,
8, 15, 6, 3, 19, 6, 1, // x^1024
21, 15, 3, 15, 10, 8, 15, 7, 2, 11, 2, 1, 13, 11, 9, 19, 9
, 8, 15, 9, 6, 22, 21, 10, // x^1088
24, 15, 6, 21, 9, 6, 15, 8, 6, 13, 9, 6, 7, 3, 1, 9, 4, 2,
11, 9, 7, 15, 3, 2, // x^1152
15, 11, 2, 12, 7, 2, 11, 9, 3, 5, 3, 2, 9, 8, 7, 15, 9, 6,
11, 10, 6, 27, 25, 9, // x^1216
12, 9, 7, 25, 10, 2, 17, 7, 5, 15, 5, 3, 31, 30, 2, 5, 3,
2, 16, 9, 7, 12, 7, 5, // x^1280
23, 16, 6, 15, 14, 2, 20, 17, 15, 15, 14, 2, 12, 9, 3, 21,
11, 3, 8, 3, 2, 15, 6, 1, // x^1344
17, 14, 6, 5, 3, 2, 15, 9, 5, 19, 18, 10, 11, 5, 1, 17, 15
, 5, 8, 3, 1, 14, 13, 6, // x^1408
10, 9, 6, 11, 6, 2, 11, 10, 6, 14, 13, 7, 11, 3, 2, 9, 4,
2, 12, 9, 3, 11, 4, 1, // x^1472
11, 10, 2, 9, 8, 6, 13, 11, 4, 8, 3, 2, 10, 9, 3, 13, 10,
3, 18, 17, 7, 21, 6, 2, // x^1536
11, 7, 1, 19, 12, 2, 8, 5, 2, 21, 10, 7, 20, 9, 2, 21, 19,
13, 12, 7, 5, 14, 11, 1, // x^1600
15, 13, 1, 13, 4, 3, 13, 11, 5, 17, 15, 3, 7, 5, 1, 18, 13
, 1, 19, 15, 10, 17, 9, 6, // x^1664
5, 4, 3, 11, 6, 2, 15, 8, 6, 15, 6, 3, 14, 11, 3, 15, 12,
5, 17, 14, 10, 11, 10, 5, // x^1728
19, 14, 6, 19, 18, 2, 6, 3, 2, 8, 3, 2, 25, 6, 5, 10, 9, 3
, 23, 21, 6, 17, 14, 3, // x^1792
22, 5, 2, 19, 16, 9, 23, 18, 1, 7, 5, 1, 18, 13, 7, 21, 10
, 2, 16, 13, 3, 11, 9, 4, // x^1856
11, 9, 1, 10, 5, 2, 15, 4, 2, 17, 13, 2, 26, 11, 2, 12, 11
, 1, 20, 15, 10, 11, 3, 2, // x^1920
17, 16, 7, 15, 10, 1, 27, 22, 18, 15, 14, 6, 17, 15, 2, 25
, 19, 14, 25, 19, 17, 13, 11, 5, // x^1984
6, 3, 2, 13, 10, 6, 26, 23, 13, 21, 15, 7, 40, 35, 9, 7, 6
, 2, 7, 2, 1, 19, 14, 13, // x^2048
13, 12, 3, 17, 9, 2, 13, 10, 3, 4, 3, 1, 18, 11, 5, 19, 4,
2, 19, 15, 9, 16, 13, 7, // x^2112
17, 14, 6, 23, 9, 1, 15, 12, 9, 13, 7, 3, 24, 13, 7, 31,
25, 14, 11, 9, 3, 15, 8, 1, // x^2176
11, 10, 5, 8, 5, 3, 20, 15, 5, 21, 16, 6, 24, 7, 2, 21, 19
, 5, 19, 17, 4, 23, 7, 1, // x^2240
9, 4, 3, 14, 9, 6, 15, 7, 2, 21, 10, 9, 13, 4, 2, 17, 16,
7, 15, 10, 1, 8, 7, 5, // x^2304
19, 6, 4, 13, 11, 5, 15, 9, 2, 15, 10, 8, 27, 26, 14, 23,
20, 2, 19, 10, 8, 13, 11, 8, // x^2368
7, 5, 4, 21, 19, 1, 31, 13, 3, 20, 19, 17, 23, 6, 4, 23, 6
, 5, 21, 16, 6, 29, 22, 19, // x^2432
12, 7, 5, 21, 10, 4, 12, 5, 3, 5, 4, 3, 12, 3, 1, 20, 5, 2
, 23, 13, 9, 12, 3, 1, // x^2496
19, 8, 6, 29, 21, 7, 31, 15, 13, 19, 9, 4, 21, 10, 9, 21,
20, 6, 28, 3, 2, 9, 3, 1, // x^2560
8, 5, 2, 7, 2, 1, 25, 19, 12, 15, 12, 5, 14, 13, 7, 15, 11
, 2, 17, 8, 7, 15, 10, 4, // x^2624
19, 5, 3, 23, 11, 9, 15, 8, 1, 19, 11, 5, 27, 21, 19, 18,
7, 1, 15, 9, 4, 21, 10, 6, // x^2688
17, 15, 12, 12, 9, 7, 21, 12, 7, 25, 18, 1, 21, 7, 5, 16,
3, 1, 19, 18, 10, 15, 4, 2, // x^2752
29, 26, 7, 25, 19, 15, 7, 3, 2, 29, 21, 15, 12, 7, 2, 17,
14, 6, 15, 13, 1, 21, 19, 8, // x^2816
15, 14, 10, 27, 18, 1, 20, 15, 9, 15, 8, 1, 15, 13, 3, 21,
17, 15, 21, 5, 2, 13, 10, 6, // x^2880
11, 4, 1, 29, 6, 1, 27, 15, 6, 16, 9, 2, 19, 9, 5, 24, 21,
11, 5, 3, 2, 5, 3, 2, // x^2944
17, 13, 2, 12, 3, 2, 29, 27, 4, 21, 10, 3, 17, 9, 6, 23, 3
, 1, 15, 12, 9, 15, 13, 1, // x^3008
38, 25, 9, 32, 3, 2, 17, 15, 4, 27, 21, 3, 18, 3, 2, 5, 4,
3, 25, 11, 9, 11, 10, 5, // x^3072
21, 19, 16, 20, 13, 11, 33, 29, 14, 23, 9, 5, 17, 15, 1,
18, 17, 11, 30, 19, 11, 15, 12, 10, // x^3136
23, 21, 8, 21, 17, 6, 7, 6, 2, 33, 31, 18, 13, 10, 5, 11,
10, 2, 25, 8, 7, 11, 6, 4, // x^3200
16, 13, 3, 21, 11, 3, 23, 19, 1, 12, 9, 7, 12, 3, 2, 15, 8
, 1, 31, 26, 2, 17, 5, 2, // x^3264
23, 10, 1, 16, 15, 6, 21, 18, 11, 19, 14, 13, 19, 17, 3,
14, 9, 3, 17, 10, 4, 17, 9, 2, // x^3328
11, 10, 5, 30, 27, 15, 21, 20, 19, 18, 15, 5, 7, 5, 1, 11,
9, 1, 21, 9, 3, 23, 13, 6, // x^3392
14, 13, 6, 16, 15, 6, 28, 27, 1, 22, 15, 6, 25, 2, 1, 27,
16, 1, 17, 11, 6, 19, 18, 9, // x^3456
11, 6, 3, 17, 14, 7, 19, 15, 13, 12, 11, 1, 35, 21, 4, 23,
17, 10, 37, 35, 6, 32, 29, 3, // x^3520
25, 18, 7, 12, 7, 5, 21, 14, 2, 15, 9, 6, 17, 3, 2, 21, 12
, 10, 19, 10, 3, 25, 12, 10, // x^3584
38, 33, 14, 9, 5, 2, 15, 14, 10, 25, 18, 7, 29, 27, 12, 26
, 17, 5, 20, 15, 10, 23, 7, 2, // x^3648
17, 12, 11, 35, 24, 14, 19, 17, 8, 14, 13, 7, 32, 13, 11,
36, 33, 22, 14, 13, 1, 13, 12, 7, // x^3712
17, 15, 11, 9, 4, 2, 33, 22, 18, 27, 14, 2, 9, 4, 2, 23, 9
, 1, 14, 7, 2, 7, 5, 4, // x^3776
29, 13, 6, 20, 7, 5, 24, 23, 21, 29, 18, 4, 19, 13, 9, 19,
13, 2, 35, 13, 2, 27, 9, 1, // x^3840
29, 18, 13, 39, 25, 3, 19, 15, 9, 10, 3, 2, 27, 5, 1, 45,
42, 6, 15, 7, 5, 17, 13, 2, // x^3904
24, 11, 2, 15, 13, 8, 8, 7, 5, 15, 5, 3, 31, 29, 28, 11, 6
, 5, 29, 15, 2, 25, 18, 14, // x^3968
36, 3, 1, 19, 5, 2, 27, 8, 6, 31, 18, 17, 24, 9, 6, 33, 32
, 23, 16, 9, 7, 15, 13, 6, // x^4032
29, 20, 15, 21, 5, 2, 21, 17, 6, 33, 29, 7, 13, 10, 6, 15,
9, 6, 15, 7, 2, 27, 15, 1, // x^4096
30, 13, 3, 23, 12, 1, 26, 17, 9, 31, 2, 1, 31, 29, 15, 15,
10, 1, 25, 13, 3, 27, 18, 12, // x^4160
17, 10, 6, 26, 15, 5, 29, 15, 7, 15, 11, 5, 12, 5, 2, 15,
6, 3, 13, 3, 2, 8, 3, 2, // x^4224
18, 13, 7, 31, 6, 1, 11, 6, 2, 15, 13, 8, 15, 14, 5, 11, 8
, 1, 17, 14, 5, 5, 4, 3, // x^4288
14, 5, 2, 12, 7, 2, 21, 5, 2, 21, 20, 14, 20, 17, 15, 18,
11, 5, 8, 7, 5, 33, 27, 20, // x^4352
21, 4, 2, 27, 12, 6, 18, 7, 1, 27, 19, 17, 20, 19, 5, 37,
35, 3, 9, 8, 7, 31, 10, 6, // x^4416
21, 19, 13, 25, 5, 3, 26, 21, 14, 11, 9, 8, 24, 9, 7, 13,
3, 1, 30, 7, 2, 28, 21, 15, // x^4480
38, 35, 13, 17, 10, 7, 12, 9, 6, 12, 3, 1, 39, 25, 23, 23,
13, 9, 25, 11, 7, 25, 14, 7, // x^4544
34, 27, 18, 14, 13, 7, 22, 17, 6, 26, 19, 9, 19, 15, 9, 21
, 16, 11, 17, 14, 1, 23, 20, 13, // x^4608
27, 23, 5, 26, 23, 10, 19, 16, 2, 25, 8, 7, 8, 5, 3, 27,
25, 4, 37, 6, 5, 27, 25, 23, // x^4672
10, 9, 3, 13, 7, 6, 18, 17, 11, 11, 8, 1, 25, 16, 6, 24,
19, 9, 26, 21, 14, 15, 10, 1, // x^4736
19, 14, 6, 29, 5, 2, 28, 11, 9, 25, 17, 3, 27, 23, 6, 30,
29, 7, 29, 18, 4, 29, 19, 11, // x^4800
13, 4, 2, 33, 31, 25, 25, 16, 3, 33, 30, 5, 25, 21, 2, 28,
27, 6, 27, 23, 21, 29, 22, 17, // x^4864
24, 9, 2, 32, 21, 7, 35, 21, 8, 21, 19, 12, 27, 18, 15, 30
, 29, 7, 11, 9, 5, 29, 9, 3, // x^4928
27, 22, 15, 19, 6, 4, 29, 11, 5, 25, 20, 6, 26, 25, 17, 42
, 7, 1, 23, 16, 9, 15, 8, 6, // x^4992
17, 15, 7, 21, 10, 3, 15, 12, 9, 33, 23, 14, 25, 6, 2, 24,
5, 3, 34, 15, 10, 22, 9, 6, // x^5056
21, 12, 11, 25, 5, 3, 21, 7, 6, 22, 21, 3, 19, 18, 13, 30,
13, 2, 42, 33, 9, 33, 27, 5, // x^5120
24, 15, 6, 27, 25, 4, 15, 11, 5, 15, 8, 1, 35, 31, 13, 15,
11, 5, 24, 21, 3, 20, 11, 5, // x^5184
11, 8, 2, 33, 27, 19, 23, 22, 2, 27, 19, 2, 29, 15, 1, 21,
11, 2, 33, 27, 21, 27, 18, 1, // x^5248
9, 5, 2, 16, 11, 9, 29, 18, 10, 13, 11, 1, 11, 10, 1, 8, 3
, 2, 27, 6, 5, 22, 3, 2, // x^5312
19, 17, 3, 30, 27, 9, 23, 21, 8, 17, 11, 10, 23, 20, 1, 19
, 11, 1, 19, 18, 3, 7, 4, 1, // x^5376
17, 15, 4, 7, 3, 2, 33, 17, 3, 30, 23, 1, 34, 31, 19, 16,
15, 13, 37, 34, 23, 24, 15, 10, // x^5440
43, 33, 15, 21, 14, 10, 15, 5, 2, 21, 15, 3, 13, 10, 3, 21
, 19, 9, 13, 11, 4, 20, 19, 1, // x^5504
13, 11, 6, 10, 5, 2, 25, 18, 14, 20, 5, 3, 11, 10, 2, 15,
9, 8, 55, 46, 10, 33, 22, 7, // x^5568
27, 23, 6, 13, 9, 7, 29, 20, 7, 8, 5, 3, 22, 5, 2, 30, 15,
6, 21, 18, 14, 17, 15, 5, // x^5632
29, 27, 23, 21, 15, 8, 27, 12, 9, 31, 29, 11, 26, 25, 10,
40, 17, 2, 41, 20, 11, 26, 21, 14, // x^5696
27, 25, 14, 10, 9, 3, 32, 11, 2, 25, 24, 7, 25, 18, 10, 21
, 11, 8, 21, 20, 7, 29, 23, 10, // x^5760
21, 14, 3, 19, 12, 1, 25, 22, 6, 33, 13, 11, 25, 7, 6, 43,
10, 1, 17, 15, 7, 23, 17, 10, // x^5824
21, 18, 13, 23, 14, 2, 19, 8, 6, 23, 15, 6, 27, 11, 10, 19
, 15, 10, 21, 10, 3, 23, 10, 4, // x^5888
30, 23, 1, 32, 19, 5, 33, 22, 13, 16, 15, 6, 16, 7, 2, 27,
4, 1, 23, 21, 14, 25, 23, 2, // x^5952
37, 35, 25, 21, 14, 4, 18, 9, 6, 17, 7, 1, 29, 9, 2, 23,
21, 12, 30, 27, 15, 35, 34, 2, // x^6016
39, 33, 26, 44, 21, 14, 25, 11, 5, 17, 15, 8, 7, 6, 1, 23,
18, 11, 28, 15, 13, 19, 8, 6, // x^6080
23, 10, 3, 20, 11, 2, 13, 11, 6, 35, 12, 1, 4, 3, 1, 34,
15, 2, 17, 7, 5, 26, 7, 1, // x^6144
28, 27, 13, 38, 15, 10, 20, 11, 2, 29, 15, 1, 39, 13, 12,
20, 5, 2, 29, 10, 7, 25, 23, 14, // x^6208
39, 30, 9, 13, 4, 2, 17, 3, 1, 11, 10, 2, 18, 7, 2, 11, 10
, 5, 17, 16, 7, 17, 10, 6, // x^6272
9, 7, 5, 34, 25, 5, 35, 19, 10, 13, 3, 1, 35, 33, 14, 29,
28, 10, 15, 6, 1, 22, 15, 9, // x^6336
21, 15, 2, 21, 11, 4, 13, 11, 1, 31, 9, 1, 28, 27, 5, 34,
29, 7, 39, 34, 10, 37, 12, 3, // x^6400
31, 12, 10, 29, 15, 7, 29, 18, 5, 26, 13, 7, 21, 18, 14,
25, 23, 8, 31, 25, 17, 25, 22, 6, // x^6464
31, 30, 2, 11, 10, 1, 21, 13, 7, 21, 5, 2, 23, 15, 9, 29,
27, 13, 37, 29, 11, 16, 7, 2, // x^6528
25, 10, 9, 19, 15, 1, 27, 22, 6, 19, 13, 11, 19, 15, 1, 27
, 25, 19, 37, 23, 7, 45, 42, 1, // x^6592
21, 19, 16, 9, 4, 2, 33, 9, 3, 15, 14, 9, 27, 20, 17, 43,
32, 9, 25, 19, 16, 19, 15, 1, // x^6656
24, 15, 6, 26, 21, 5, 29, 7, 3, 55, 32, 9, 45, 19, 7, 11,
10, 6, 31, 26, 2, 12, 9, 7, // x^6720
21, 8, 2, 27, 14, 2, 29, 21, 15, 11, 8, 2, 37, 15, 7, 18,
15, 10, 25, 11, 6, 16, 15, 1, // x^6784
27, 25, 24, 26, 25, 1, 37, 19, 13, 22, 5, 2, 21, 14, 10,
35, 32, 25, 14, 9, 3, 29, 22, 18, // x^6848
30, 29, 17, 11, 5, 2, 25, 13, 2, 31, 30, 19, 24, 11, 9, 29
, 17, 11, 36, 13, 11, 25, 15, 12, // x^6912
8, 3, 1, 8, 7, 5, 37, 31, 30, 23, 21, 8, 32, 21, 19, 14, 9
, 3, 35, 32, 17, 19, 18, 9, // x^6976
8, 3, 2, 27, 11, 9, 27, 26, 11, 33, 25, 6, 23, 10, 7, 22,
15, 10, 19, 13, 9, 19, 18, 7, // x^7040
39, 17, 4, 27, 24, 10, 11, 5, 2, 37, 26, 17, 27, 18, 16,
32, 5, 2, 27, 17, 13, 15, 10, 4, // x^7104
35, 5, 2, 17, 15, 5, 19, 13, 2, 16, 3, 2, 33, 13, 3, 37,
23, 16, 27, 26, 9, 13, 10, 6, // x^7168
33, 31, 21, 33, 27, 2, 29, 14, 6, 29, 23, 3, 29, 23, 21,
15, 8, 1, 15, 12, 10, 35, 12, 9, // x^7232
33, 14, 2, 17, 7, 4, 22, 21, 7, 41, 36, 19, 23, 10, 4, 37,
6, 4, 25, 23, 17, 37, 7, 2, // x^7296
37, 30, 17, 25, 24, 3, 35, 28, 10, 41, 30, 26, 34, 21, 5,
33, 28, 3, 20, 5, 3, 23, 18, 2, // x^7360
19, 13, 11, 41, 22, 16, 31, 26, 9, 33, 27, 21, 19, 9, 5,
13, 3, 1, 35, 23, 9, 18, 13, 7, // x^7424
30, 19, 7, 22, 21, 15, 21, 20, 14, 27, 8, 1, 21, 18, 14,
23, 13, 7, 32, 15, 2, 21, 16, 6, // x^7488
23, 21, 12, 45, 17, 2, 22, 21, 3, 19, 9, 7, 18, 13, 1, 42,
21, 14, 23, 13, 7, 17, 8, 3, // x^7552
41, 21, 3, 15, 5, 3, 41, 40, 11, 51, 46, 10, 45, 10, 1, 19
, 18, 2, 39, 25, 10, 31, 21, 14, // x^7616
9, 2, 1, 54, 3, 2, 29, 3, 2, 37, 33, 10, 30, 13, 7, 30, 23
, 5, 39, 5, 1, 27, 9, 3, // x^7680
35, 16, 6, 17, 16, 15, 15, 12, 10, 27, 22, 5, 27, 25, 4,
21, 6, 3, 22, 11, 3, 33, 28, 27, // x^7744
35, 30, 2, 32, 23, 21, 27, 18, 15, 41, 39, 36, 7, 4, 2, 47
, 31, 29, 11, 10, 5, 25, 24, 10, // x^7808
20, 3, 2, 39, 36, 14, 37, 19, 3, 33, 29, 23, 34, 31, 21,
12, 3, 2, 19, 13, 1, 27, 22, 18, // x^7872
25, 19, 17, 12, 9, 7, 45, 39, 7, 45, 34, 25, 7, 3, 2, 20,
19, 5, 23, 15, 5, 40, 23, 21, // x^7936
14, 7, 1, 19, 13, 2, 19, 13, 12, 27, 13, 12, 44, 5, 3, 37,
18, 2, 26, 25, 17, 16, 3, 1, // x^8000
23, 22, 17, 31, 30, 25, 21, 14, 11, 19, 15, 13, 39, 13, 7,
30, 23, 3, 27, 16, 5, 27, 23, 9, // x^8064
23, 11, 6, 39, 14, 11, 25, 10, 8, 32, 11, 2, 30, 23, 17,
15, 12, 2, 8, 3, 2, 25, 24, 19, // x^8128
11, 3, 2, 28, 27, 17, 29, 25, 14, 52, 45, 10, 25, 16, 6,
43, 32, 21, 32, 27, 6, 9, 5, 2, // x^8192
18, 15, 3, 19, 13, 11, 27, 24, 17, 39, 36, 25, 22, 15, 9,
14, 13, 7, 25, 15, 13, 32, 21, 14, // x^8256
15, 6, 3, 32, 25, 23, 30, 19, 9, 27, 5, 4, 37, 19, 6, 32,
17, 15, 45, 44, 30, 41, 39, 5, // x^8320
37, 23, 14, 33, 10, 2, 27, 15, 1, 35, 18, 14, 15, 14, 5,
35, 17, 4, 45, 39, 17, 19, 4, 2, // x^8384
17, 11, 1, 29, 28, 11, 20, 9, 2, 40, 33, 22, 33, 31, 28,
17, 15, 13, 18, 9, 6, 21, 17, 6, // x^8448
15, 13, 8, 34, 15, 5, 30, 21, 5, 21, 6, 3, 13, 6, 3, 25,
19, 3, 35, 24, 10, 33, 27, 4, // x^8512
28, 15, 13, 15, 4, 2, 19, 10, 3, 31, 5, 2, 29, 10, 1, 21,
13, 3, 28, 25, 10, 19, 9, 1, // x^8576
32, 15, 13, 23, 5, 4, 21, 14, 3, 47, 44, 33, 22, 19, 11, 4
, 3, 2, 41, 32, 3, 23, 10, 4, // x^8640
31, 17, 6, 39, 14, 4, 29, 19, 11, 29, 23, 12, 32, 7, 2, 25
, 20, 7, 25, 20, 6, 39, 20, 2, // x^8704
30, 13, 3, 27, 17, 5, 13, 7, 1, 35, 33, 24, 45, 12, 11, 30
, 29, 11, 27, 9, 4, 27, 10, 8, // x^8768
26, 19, 9, 26, 25, 7, 24, 9, 2, 25, 14, 6, 15, 9, 6, 17, 8
, 6, 19, 14, 6, 15, 9, 6, // x^8832
33, 22, 16, 33, 4, 3, 14, 5, 2, 37, 12, 7, 51, 4, 2, 36, 9
, 6, 43, 13, 9, 41, 10, 6, // x^8896
40, 25, 10, 18, 17, 1, 33, 32, 31, 35, 29, 2, 17, 3, 1, 39
, 34, 1, 27, 14, 2, 12, 7, 5, // x^8960
29, 11, 10, 23, 8, 2, 9, 8, 6, 35, 6, 2, 28, 19, 17, 31,
17, 7, 23, 21, 8, 32, 29, 11, // x^9024
45, 19, 1, 9, 6, 4, 23, 16, 10, 11, 3, 2, 33, 4, 2, 45, 38
, 6, 17, 10, 7, 33, 31, 1, // x^9088
27, 26, 11, 47, 33, 24, 9, 7, 5, 35, 25, 5, 39, 25, 22, 21
, 14, 1, 35, 25, 4, 33, 29, 7, // x^9152
22, 15, 3, 15, 10, 4, 43, 37, 30, 33, 26, 14, 21, 18, 13,
31, 24, 2, 35, 10, 9, 21, 14, 8, // x^9216
35, 21, 7, 49, 18, 8, 17, 11, 7, 37, 18, 13, 19, 6, 4, 39,
17, 14, 13, 4, 3, 23, 7, 2, // x^9280
49, 43, 18, 29, 17, 15, 27, 13, 9, 21, 19, 16, 55, 22, 8,
21, 14, 8, 17, 5, 3, 51, 44, 5, // x^9344
31, 26, 15, 28, 23, 1, 38, 7, 1, 23, 5, 1, 17, 11, 6, 29,
24, 11, 18, 13, 1, 28, 15, 6, // x^9408
19, 11, 6, 22, 9, 6, 52, 43, 25, 25, 22, 14, 23, 21, 20,
35, 19, 5, 37, 18, 13, 45, 40, 15, // x^9472
18, 9, 2, 25, 12, 7, 29, 17, 15, 19, 15, 6, 39, 17, 16, 13
, 5, 2, 37, 33, 22, 31, 26, 6, // x^9536
43, 32, 9, 11, 4, 1, 27, 13, 2, 49, 26, 14, 29, 25, 7, 36,
29, 27, 15, 8, 1, 19, 6, 4, // x^9600
14, 13, 1, 25, 8, 2, 31, 17, 7, 30, 23, 5, 33, 7, 3, 31,
24, 21, 19, 16, 2, 35, 21, 1, // x^9664
17, 9, 3, 25, 6, 2, 20, 9, 2, 36, 27, 21, 7, 3, 2, 27, 19,
17, 37, 4, 2, 30, 5, 2, // x^9728
15, 7, 6, 36, 9, 2, 42, 17, 3, 56, 49, 47, 41, 23, 22, 24,
19, 1, 38, 37, 9, 27, 26, 21, // x^9792
42, 41, 10, 43, 32, 21, 46, 33, 22, 13, 10, 3, 39, 37, 25,
49, 47, 13, 25, 23, 10, 36, 15, 1, // x^9856
35, 32, 21, 13, 11, 3, 35, 28, 5, 33, 6, 4, 39, 38, 26, 21
, 10, 2, 42, 35, 15, 49, 18, 14, // x^9920
39, 38, 31, 22, 21, 1, 15, 14, 6, 31, 30, 11, 30, 15, 10,
36, 3, 2, 21, 19, 5, 27, 10, 7, // x^9984
7, 4, 2, 19, 13, 9 // x^10000
};
public BigInteger PolynomialValue { get; private set; }
public IrreduciblePolynomial(int degreeOfIrreduciblePolynomial) {
if (!IsValidDegree(degreeOfIrreduciblePolynomial)) {
throw new ArgumentException();
}
PolynomialValue = BigInteger.Zero.SetBit(degreeOfIrreduciblePolynomial);
for (int i = 0; i < InnerTermsPerPolynomial; i++) {
PolynomialValue =
PolynomialValue.SetBit(
_TermPowers[InnerTermsPerPolynomial*((degreeOfIrreduciblePolynomial/8) - 1) + i]);
}
PolynomialValue = PolynomialValue.SetBit(0);
Degree = degreeOfIrreduciblePolynomial;
}
public int Degree { get; private set; }
public int SizeInBytes {
get { return Degree/8; }
}
public static IrreduciblePolynomial CreateOfByteSize(int byteSize) {
return new IrreduciblePolynomial(byteSize*8);
}
public static int MaxDegree {
get { return (_TermPowers.Length/InnerTermsPerPolynomial)*8; }
}
public static bool IsValidDegree(int degree) {
return (8 <= degree) && (degree <= MaxDegree) && ((degree%8) == 0);
}
public override string ToString() {
return PolynomialValue.ToPolynomialString();
}
public override bool Equals(object obj) {
var other = obj as IrreduciblePolynomial;
if (other == null) {
return base.Equals(obj);
}
return PolynomialValue.Equals(other.PolynomialValue);
}
public override int GetHashCode() {
return PolynomialValue.GetHashCode();
}
}
}