This file is indexed.

/usr/share/gap/doc/ref/chap59.html is in gap-doc 4r8p8-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  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
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (ref) - Chapter 59: Finite Fields</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap59"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap58.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap60.html">[Next Chapter]</a>&nbsp;  </div>

<p id="mathjaxlink" class="pcenter"><a href="chap59_mj.html">[MathJax on]</a></p>
<p><a id="X7893ABF67A028802" name="X7893ABF67A028802"></a></p>
<div class="ChapSects"><a href="chap59.html#X7893ABF67A028802">59 <span class="Heading">Finite Fields</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap59.html#X7B9DCCCC83400B47">59.1 <span class="Heading">Finite Field Elements</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X7D3DF32C84FEBD25">59.1-1 IsFFE</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X7AA52FAF7EDEDD56">59.1-2 Z</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X8612BCEA816CF1B9">59.1-3 IsLexOrderedFFE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap59.html#X7A79399283EF78D0">59.2 <span class="Heading">Operations for Finite Field Elements</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X828E846E7C1EA3DD">59.2-1 DegreeFFE</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X7B049A3478B369E4">59.2-2 LogFFE</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X79F48E337FC2746A">59.2-3 IntFFE</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X7DABD827848BCC2A">59.2-4 IntFFESymm</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X8009968782F18888">59.2-5 IntVecFFE</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X807959EE82CED148">59.2-6 AsInternalFFE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap59.html#X81B54A8378734C33">59.3 <span class="Heading">Creating Finite Fields</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X7979F51D7C43AB05">59.3-1 DefaultField</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X8592DBB086A8A9BE">59.3-2 GaloisField</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X788B1ECD83C70516">59.3-3 PrimitiveRoot</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap59.html#X7A5F075185CE5B06">59.4 <span class="Heading">Frobenius Automorphisms</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X8758E4AB7D0A1955">59.4-1 FrobeniusAutomorphism</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap59.html#X869919BB7EBE5741">59.5 <span class="Heading">Conway Polynomials</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X7C2425A786F09054">59.5-1 ConwayPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X78A7C1247E129AD9">59.5-2 IsCheapConwayPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X7ECC593583E68A6C">59.5-3 RandomPrimitivePolynomial</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap59.html#X78EE3656879C3B88">59.6 <span class="Heading">Printing, Viewing and Displaying Finite Field Elements</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap59.html#X80DAAA5E7C79C94C">59.6-1 ViewObj</a></span>
</div></div>
</div>

<h3>59 <span class="Heading">Finite Fields</span></h3>

<p>This chapter describes the special functionality which exists in <strong class="pkg">GAP</strong> for finite fields and their elements. Of course the general functionality for fields (see Chapter <a href="chap58.html#X80A8E676814A19FD"><span class="RefLink">58</span></a>) also applies to finite fields.</p>

<p>In the following, the term <em>finite field element</em> is used to denote <strong class="pkg">GAP</strong> objects in the category <code class="func">IsFFE</code> (<a href="chap59.html#X7D3DF32C84FEBD25"><span class="RefLink">59.1-1</span></a>), and <em>finite field</em> means a field consisting of such elements. Note that in principle we must distinguish these fields from (abstract) finite fields. For example, the image of the embedding of a finite field into a field of rational functions in the same characteristic is of course a finite field but its elements are not in <code class="func">IsFFE</code> (<a href="chap59.html#X7D3DF32C84FEBD25"><span class="RefLink">59.1-1</span></a>), and in fact <strong class="pkg">GAP</strong> does currently not support such fields.</p>

<p>Special representations exist for row vectors and matrices over small finite fields (see sections <a href="chap23.html#X8679F7DD7DFCBD9C"><span class="RefLink">23.3</span></a> and <a href="chap24.html#X873822B6830CE367"><span class="RefLink">24.14</span></a>).</p>

<p><a id="X7B9DCCCC83400B47" name="X7B9DCCCC83400B47"></a></p>

<h4>59.1 <span class="Heading">Finite Field Elements</span></h4>

<p><a id="X7D3DF32C84FEBD25" name="X7D3DF32C84FEBD25"></a></p>

<h5>59.1-1 IsFFE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsFFE</code>( <var class="Arg">obj</var> )</td><td class="tdright">(&nbsp;category&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsFFECollection</code>( <var class="Arg">obj</var> )</td><td class="tdright">(&nbsp;category&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsFFECollColl</code>( <var class="Arg">obj</var> )</td><td class="tdright">(&nbsp;category&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsFFECollCollColl</code>( <var class="Arg">obj</var> )</td><td class="tdright">(&nbsp;category&nbsp;)</td></tr></table></div>
<p>Objects in the category <code class="func">IsFFE</code> are used to implement elements of finite fields. In this manual, the term <em>finite field element</em> always means an object in <code class="func">IsFFE</code>. All finite field elements of the same characteristic form a family in <strong class="pkg">GAP</strong> (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>). Any collection of finite field elements (see <code class="func">IsCollection</code> (<a href="chap30.html#X79C9FC7F86E2738C"><span class="RefLink">30.1-1</span></a>)) lies in <code class="func">IsFFECollection</code>, and a collection of such collections (e.g., a matrix of finite field elements) lies in <code class="func">IsFFECollColl</code>.</p>

<p><a id="X7AA52FAF7EDEDD56" name="X7AA52FAF7EDEDD56"></a></p>

<h5>59.1-2 Z</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; Z</code>( <var class="Arg">p^d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; Z</code>( <var class="Arg">p</var>, <var class="Arg">d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>For creating elements of a finite field, the function <code class="func">Z</code> can be used. The call <code class="code">Z(<var class="Arg">p</var>,<var class="Arg">d</var>)</code> (alternatively <code class="code">Z(<var class="Arg">p</var>^<var class="Arg">d</var>)</code>) returns the designated generator of the multiplicative group of the finite field with <var class="Arg">p^d</var> elements. <var class="Arg">p</var> must be a prime integer.</p>

<p><strong class="pkg">GAP</strong> can represent elements of all finite fields <code class="code">GF(<var class="Arg">p^d</var>)</code> such that either (1) <var class="Arg">p^d</var> <span class="SimpleMath">&lt;= 65536</span> (in which case an extremely efficient internal representation is used); (2) d = 1, (in which case, for large <var class="Arg">p</var>, the field is represented using the machinery of residue class rings (see section <a href="chap14.html#X864BF040862409FC"><span class="RefLink">14.5</span></a>) or (3) if the Conway polynomial of degree <var class="Arg">d</var> over the field with <var class="Arg">p</var> elements is known, or can be computed (see <code class="func">ConwayPolynomial</code> (<a href="chap59.html#X7C2425A786F09054"><span class="RefLink">59.5-1</span></a>)).</p>

<p>If you attempt to construct an element of <code class="code">GF(<var class="Arg">p^d</var>)</code> for which <var class="Arg">d</var> <span class="SimpleMath">&gt; 1</span> and the relevant Conway polynomial is not known, and not necessarily easy to find (see <code class="func">IsCheapConwayPolynomial</code> (<a href="chap59.html#X78A7C1247E129AD9"><span class="RefLink">59.5-2</span></a>)), then <strong class="pkg">GAP</strong> will stop with an error and enter the break loop. If you leave this break loop by entering <code class="code">return;</code> <strong class="pkg">GAP</strong> will attempt to compute the Conway polynomial, which may take a very long time.</p>

<p>The root returned by <code class="func">Z</code> is a generator of the multiplicative group of the finite field with <var class="Arg">p^d</var> elements, which is cyclic. The order of the element is of course <var class="Arg">p^d</var> <span class="SimpleMath">-1</span>. The <var class="Arg">p^d</var> <span class="SimpleMath">-1</span> different powers of the root are exactly the nonzero elements of the finite field.</p>

<p>Thus all nonzero elements of the finite field with <var class="Arg">p^d</var> elements can be entered as <code class="code">Z(<var class="Arg">p^d</var>)^</code><span class="SimpleMath">i</span>. Note that this is also the form that <strong class="pkg">GAP</strong> uses to output those elements when they are stored in the internal representation. In larger fields, it is more convenient to enter and print elements as linear combinations of powers of the primitive element, see section <a href="chap59.html#X78EE3656879C3B88"><span class="RefLink">59.6</span></a>.</p>

<p>The additive neutral element is <code class="code">0 * Z(<var class="Arg">p</var>)</code>. It is different from the integer <code class="code">0</code> in subtle ways. First <code class="code">IsInt( 0 * Z(<var class="Arg">p</var>) )</code> (see <code class="func">IsInt</code> (<a href="chap14.html#X87AEADF07DC8303B"><span class="RefLink">14.2-1</span></a>)) is <code class="keyw">false</code> and <code class="code">IsFFE( 0 * Z(<var class="Arg">p</var>) )</code> (see <code class="func">IsFFE</code> (<a href="chap59.html#X7D3DF32C84FEBD25"><span class="RefLink">59.1-1</span></a>)) is <code class="keyw">true</code>, whereas it is just the other way around for the integer <code class="code">0</code>.</p>

<p>The multiplicative neutral element is <code class="code">Z(<var class="Arg">p</var>)^0</code>. It is different from the integer <code class="code">1</code> in subtle ways. First <code class="code">IsInt( Z(<var class="Arg">p</var>)^0 )</code> (see <code class="func">IsInt</code> (<a href="chap14.html#X87AEADF07DC8303B"><span class="RefLink">14.2-1</span></a>)) is <code class="keyw">false</code> and <code class="code">IsFFE( Z(<var class="Arg">p</var>)^0 )</code> (see <code class="func">IsFFE</code> (<a href="chap59.html#X7D3DF32C84FEBD25"><span class="RefLink">59.1-1</span></a>)) is <code class="keyw">true</code>, whereas it is just the other way around for the integer <code class="code">1</code>. Also <code class="code">1+1</code> is <code class="code">2</code>, whereas, e.g., <code class="code">Z(2)^0 + Z(2)^0</code> is <code class="code">0 * Z(2)</code>.</p>

<p>The various roots returned by <code class="func">Z</code> for finite fields of the same characteristic are compatible in the following sense. If the field <code class="code">GF(<var class="Arg">p</var>,</code><span class="SimpleMath">n</span><code class="code">)</code> is a subfield of the field <code class="code">GF(<var class="Arg">p</var>,</code><span class="SimpleMath">m</span><code class="code">)</code>, i.e., <span class="SimpleMath">n</span> divides <span class="SimpleMath">m</span>, then <code class="code">Z</code><span class="SimpleMath">(<var class="Arg">p</var>^n) =</span><code class="code">Z</code><span class="SimpleMath">(<var class="Arg">p</var>^m)^{(<var class="Arg">p</var>^m-1)/(<var class="Arg">p</var>^n-1)}</span>. Note that this is the simplest relation that may hold between a generator of <code class="code">GF(<var class="Arg">p</var>,</code><span class="SimpleMath">n</span><code class="code">)</code> and <code class="code">GF(<var class="Arg">p</var>,</code><span class="SimpleMath">m</span><code class="code">)</code>, since <code class="code">Z</code><span class="SimpleMath">(<var class="Arg">p</var>^n)</span> is an element of order <span class="SimpleMath"><var class="Arg">p</var>^m-1</span> and <code class="code">Z</code><span class="SimpleMath">(<var class="Arg">p</var>^m)</span> is an element of order <span class="SimpleMath"><var class="Arg">p</var>^n-1</span>. This is achieved by choosing <code class="code">Z(<var class="Arg">p</var>)</code> as the smallest primitive root modulo <var class="Arg">p</var> and <code class="code">Z(</code><var class="Arg">p^n</var><code class="code">)</code> as a root of the <span class="SimpleMath">n</span>-th <em>Conway polynomial</em> (see <code class="func">ConwayPolynomial</code> (<a href="chap59.html#X7C2425A786F09054"><span class="RefLink">59.5-1</span></a>)) of characteristic <var class="Arg">p</var>. Those polynomials were defined by J. H. Conway, and many of them were computed by R. A. Parker.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a:= Z( 32 );</span>
Z(2^5)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a+a;</span>
0*Z(2)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a*a;</span>
Z(2^5)^2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b := Z(3,12);</span>
z
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b*b;</span>
z2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b+b;</span>
2z
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Print(b^100,"\n");</span>
Z(3)^0+Z(3,12)^5+Z(3,12)^6+2*Z(3,12)^8+Z(3,12)^10+Z(3,12)^11
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(11,40);</span>
Error, Conway Polynomial 11^40 will need to computed and might be slow
return to continue called from
FFECONWAY.ZNC( p, d ) called from
&lt;function&gt;( &lt;arguments&gt; ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
<span class="GAPbrkprompt">brk&gt;</span>
</pre></div>

<p><a id="X8612BCEA816CF1B9" name="X8612BCEA816CF1B9"></a></p>

<h5>59.1-3 IsLexOrderedFFE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsLexOrderedFFE</code>( <var class="Arg">ffe</var> )</td><td class="tdright">(&nbsp;category&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsLogOrderedFFE</code>( <var class="Arg">ffe</var> )</td><td class="tdright">(&nbsp;category&nbsp;)</td></tr></table></div>
<p>Elements of finite fields can be compared using the operators <code class="code">=</code> and <code class="code">&lt;</code>. The call <code class="code"><var class="Arg">a</var> = <var class="Arg">b</var></code> returns <code class="keyw">true</code> if and only if the finite field elements <var class="Arg">a</var> and <var class="Arg">b</var> are equal. Furthermore <code class="code"><var class="Arg">a</var> &lt; <var class="Arg">b</var></code> tests whether <var class="Arg">a</var> is smaller than <var class="Arg">b</var>. The exact behaviour of this comparison depends on which of two categories the field elements belong to:</p>

<p>Finite field elements are ordered in <strong class="pkg">GAP</strong> (by <code class="func">\&lt;</code> (<a href="chap31.html#X7EF67D047F03CA6F"><span class="RefLink">31.11-1</span></a>)) first by characteristic and then by their degree (i.e. the sizes of the smallest fields containing them). Amongst irreducible elements of a given field, the ordering depends on which of these categories the elements of the field belong to (all irreducible elements of a given field should belong to the same one)</p>

<p>Elements in <code class="func">IsLexOrderedFFE</code> are ordered lexicographically by their coefficients with respect to the canonical basis of the field.</p>

<p>Elements in <code class="func">IsLogOrderedFFE</code> are ordered according to their discrete logarithms with respect to the <code class="func">PrimitiveElement</code> (<a href="chap58.html#X86DB31B57FB4F570"><span class="RefLink">58.2-3</span></a>) attribute of the field. For the comparison of finite field elements with other <strong class="pkg">GAP</strong> objects, see <a href="chap4.html#X7A274A1F8553B7E6"><span class="RefLink">4.12</span></a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z( 16 )^10 = Z( 4 )^2;  # illustrates embedding of GF(4) in GF(16)</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">0 &lt; 0*Z(101);</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(256) &gt; Z(101);</span>
false
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(2,20) &lt; Z(2,20)^2; # this illustrates the lexicographic ordering</span>
false
</pre></div>

<p><a id="X7A79399283EF78D0" name="X7A79399283EF78D0"></a></p>

<h4>59.2 <span class="Heading">Operations for Finite Field Elements</span></h4>

<p>Since finite field elements are scalars, the operations <code class="func">Characteristic</code> (<a href="chap31.html#X81278E53800BF64D"><span class="RefLink">31.10-1</span></a>), <code class="func">One</code> (<a href="chap31.html#X8046262384895B2A"><span class="RefLink">31.10-2</span></a>), <code class="func">Zero</code> (<a href="chap31.html#X8040AC7A79FFC442"><span class="RefLink">31.10-3</span></a>), <code class="func">Inverse</code> (<a href="chap31.html#X78EE524E83624057"><span class="RefLink">31.10-8</span></a>), <code class="func">AdditiveInverse</code> (<a href="chap31.html#X84BB723C81D55D63"><span class="RefLink">31.10-9</span></a>), <code class="func">Order</code> (<a href="chap31.html#X84F59A2687C62763"><span class="RefLink">31.10-10</span></a>) can be applied to them (see <a href="chap31.html#X7C2B0C1280237CB0"><span class="RefLink">31.10</span></a>). Contrary to the situation with other scalars, <code class="func">Order</code> (<a href="chap31.html#X84F59A2687C62763"><span class="RefLink">31.10-10</span></a>) is defined also for the zero element in a finite field, with value <code class="code">0</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Characteristic( Z( 16 )^10 );  Characteristic( Z( 9 )^2 );</span>
2
3
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Characteristic( [ Z(4), Z(8) ] );</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">One( Z(9) );  One( 0*Z(4) );</span>
Z(3)^0
Z(2)^0
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Inverse( Z(9) );  AdditiveInverse( Z(9) );</span>
Z(3^2)^7
Z(3^2)^5
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Order( Z(9)^7 );</span>
8
</pre></div>

<p><a id="X828E846E7C1EA3DD" name="X828E846E7C1EA3DD"></a></p>

<h5>59.2-1 DegreeFFE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DegreeFFE</code>( <var class="Arg">z</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DegreeFFE</code>( <var class="Arg">vec</var> )</td><td class="tdright">(&nbsp;method&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DegreeFFE</code>( <var class="Arg">mat</var> )</td><td class="tdright">(&nbsp;method&nbsp;)</td></tr></table></div>
<p><code class="func">DegreeFFE</code> returns the degree of the smallest finite field <var class="Arg">F</var> containing the element <var class="Arg">z</var>, respectively all elements of the row vector <var class="Arg">vec</var> over a finite field (see <a href="chap23.html#X82C7E6CF7BA03391"><span class="RefLink">23</span></a>), or the matrix <var class="Arg">mat</var> over a finite field (see <a href="chap24.html#X812CCAB278643A59"><span class="RefLink">24</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">DegreeFFE( Z( 16 )^10 );</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">DegreeFFE( Z( 16 )^11 );</span>
4
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">DegreeFFE( [ Z(2^13), Z(2^10) ] );</span>
130
</pre></div>

<p><a id="X7B049A3478B369E4" name="X7B049A3478B369E4"></a></p>

<h5>59.2-2 LogFFE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; LogFFE</code>( <var class="Arg">z</var>, <var class="Arg">r</var> )</td><td class="tdright">(&nbsp;operation&nbsp;)</td></tr></table></div>
<p><code class="func">LogFFE</code> returns the discrete logarithm of the element <var class="Arg">z</var> in a finite field with respect to the root <var class="Arg">r</var>. An error is signalled if <var class="Arg">z</var> is zero. <code class="keyw">fail</code> is returned if <var class="Arg">z</var> is not a power of <var class="Arg">r</var>.</p>

<p>The <em>discrete logarithm</em> of the element <var class="Arg">z</var> with respect to the root <var class="Arg">r</var> is the smallest nonnegative integer <span class="SimpleMath">i</span> such that <span class="SimpleMath"><var class="Arg">r</var>^i = <var class="Arg">z</var></span> holds.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">LogFFE( Z(409)^116, Z(409) );  LogFFE( Z(409)^116, Z(409)^2 );</span>
116
58
</pre></div>

<p><a id="X79F48E337FC2746A" name="X79F48E337FC2746A"></a></p>

<h5>59.2-3 IntFFE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IntFFE</code>( <var class="Arg">z</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; Int</code>( <var class="Arg">z</var> )</td><td class="tdright">(&nbsp;method&nbsp;)</td></tr></table></div>
<p><code class="func">IntFFE</code> returns the integer corresponding to the element <var class="Arg">z</var>, which must lie in a finite prime field. That is, <code class="func">IntFFE</code> returns the smallest nonnegative integer <span class="SimpleMath">i</span> such that <span class="SimpleMath">i</span><code class="code"> * One( </code><var class="Arg">z</var><code class="code"> ) = </code><var class="Arg">z</var>.</p>

<p>The correspondence between elements from a finite prime field of characteristic <span class="SimpleMath">p</span> (for <span class="SimpleMath">p &lt; 2^16</span>) and the integers between <span class="SimpleMath">0</span> and <span class="SimpleMath">p-1</span> is defined by choosing <code class="code">Z(</code><span class="SimpleMath">p</span><code class="code">)</code> the element corresponding to the smallest primitive root mod <span class="SimpleMath">p</span> (see <code class="func">PrimitiveRootMod</code> (<a href="chap15.html#X82440BB9812FF148"><span class="RefLink">15.3-3</span></a>)).</p>

<p><code class="func">IntFFE</code> is installed as a method for the operation <code class="func">Int</code> (<a href="chap14.html#X87CA734380B5F68C"><span class="RefLink">14.2-3</span></a>) with argument a finite field element.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IntFFE( Z(13) );  PrimitiveRootMod( 13 );</span>
2
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IntFFE( Z(409) );</span>
21
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IntFFE( Z(409)^116 );  21^116 mod 409;</span>
311
311
</pre></div>

<p>See also <code class="func">IntFFESymm</code> (<a href="chap59.html#X7DABD827848BCC2A"><span class="RefLink">59.2-4</span></a>).</p>

<p><a id="X7DABD827848BCC2A" name="X7DABD827848BCC2A"></a></p>

<h5>59.2-4 IntFFESymm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IntFFESymm</code>( <var class="Arg">z</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IntFFESymm</code>( <var class="Arg">vec</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<p>For a finite prime field element <var class="Arg">z</var>, <code class="func">IntFFESymm</code> returns the corresponding integer of smallest absolute value. That is, <code class="func">IntFFESymm</code> returns the integer <span class="SimpleMath">i</span> of smallest absolute value such that <span class="SimpleMath">i</span><code class="code"> * One( </code><var class="Arg">z</var><code class="code"> ) = </code><var class="Arg">z</var> holds.</p>

<p>For a vector <var class="Arg">vec</var> of FFEs, the operation returns the result of applying <code class="func">IntFFESymm</code> to every entry of the vector.</p>

<p>The correspondence between elements from a finite prime field of characteristic <span class="SimpleMath">p</span> (for <span class="SimpleMath">p &lt; 2^16</span>) and the integers between <span class="SimpleMath">-p/2</span> and <span class="SimpleMath">p/2</span> is defined by choosing <code class="code">Z(</code><span class="SimpleMath">p</span><code class="code">)</code> the element corresponding to the smallest positive primitive root mod <span class="SimpleMath">p</span> (see <code class="func">PrimitiveRootMod</code> (<a href="chap15.html#X82440BB9812FF148"><span class="RefLink">15.3-3</span></a>)) and reducing results to the <span class="SimpleMath">-p/2 .. p/2</span> range.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IntFFE(Z(13)^2);IntFFE(Z(13)^3);</span>
4
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IntFFESymm(Z(13)^2);IntFFESymm(Z(13)^3);</span>
4
-5
</pre></div>

<p>See also <code class="func">IntFFE</code> (<a href="chap59.html#X79F48E337FC2746A"><span class="RefLink">59.2-3</span></a>)</p>

<p><a id="X8009968782F18888" name="X8009968782F18888"></a></p>

<h5>59.2-5 IntVecFFE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IntVecFFE</code>( <var class="Arg">vecffe</var> )</td><td class="tdright">(&nbsp;operation&nbsp;)</td></tr></table></div>
<p>is the list of integers corresponding to the vector <var class="Arg">vecffe</var> of finite field elements in a prime field (see <code class="func">IntFFE</code> (<a href="chap59.html#X79F48E337FC2746A"><span class="RefLink">59.2-3</span></a>)).</p>

<p><a id="X807959EE82CED148" name="X807959EE82CED148"></a></p>

<h5>59.2-6 AsInternalFFE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; AsInternalFFE</code>( <var class="Arg">ffe</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<p>return an internal FFE equal to <var class="Arg">ffe</var> if one exists, otherwise <code class="code">fail</code></p>

<p><a id="X81B54A8378734C33" name="X81B54A8378734C33"></a></p>

<h4>59.3 <span class="Heading">Creating Finite Fields</span></h4>

<p><a id="X7979F51D7C43AB05" name="X7979F51D7C43AB05"></a></p>

<h5>59.3-1 DefaultField</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DefaultField</code>( <var class="Arg">list</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DefaultRing</code>( <var class="Arg">list</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p><code class="func">DefaultField</code> and <code class="func">DefaultRing</code> for finite field elements are defined to return the <em>smallest</em> field containing the given elements.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">DefaultField( [ Z(4), Z(4)^2 ] );  DefaultField( [ Z(4), Z(8) ] );</span>
GF(2^2)
GF(2^6)
</pre></div>

<p><a id="X8592DBB086A8A9BE" name="X8592DBB086A8A9BE"></a></p>

<h5>59.3-2 GaloisField</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GaloisField</code>( <var class="Arg">p^d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GF</code>( <var class="Arg">p^d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GaloisField</code>( <var class="Arg">p</var>, <var class="Arg">d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GF</code>( <var class="Arg">p</var>, <var class="Arg">d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GaloisField</code>( <var class="Arg">subfield</var>, <var class="Arg">d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GF</code>( <var class="Arg">subfield</var>, <var class="Arg">d</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GaloisField</code>( <var class="Arg">p</var>, <var class="Arg">pol</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GF</code>( <var class="Arg">p</var>, <var class="Arg">pol</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GaloisField</code>( <var class="Arg">subfield</var>, <var class="Arg">pol</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; GF</code>( <var class="Arg">subfield</var>, <var class="Arg">pol</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p><code class="func">GaloisField</code> returns a finite field. It takes two arguments. The form <code class="code">GaloisField( <var class="Arg">p</var>, <var class="Arg">d</var> )</code>, where <var class="Arg">p</var>, <var class="Arg">d</var> are integers, can also be given as <code class="code">GaloisField( <var class="Arg">p</var>^<var class="Arg">d</var> )</code>. <code class="func">GF</code> is an abbreviation for <code class="func">GaloisField</code>.</p>

<p>The first argument specifies the subfield <span class="SimpleMath">S</span> over which the new field is to be taken. It can be a prime integer or a finite field. If it is a prime <var class="Arg">p</var>, the subfield is the prime field of this characteristic.</p>

<p>The second argument specifies the extension. It can be an integer or an irreducible polynomial over the field <span class="SimpleMath">S</span>. If it is an integer <var class="Arg">d</var>, the new field is constructed as the polynomial extension w.r.t. the Conway polynomial (see <code class="func">ConwayPolynomial</code> (<a href="chap59.html#X7C2425A786F09054"><span class="RefLink">59.5-1</span></a>)) of degree <var class="Arg">d</var> over <span class="SimpleMath">S</span>. If it is an irreducible polynomial <var class="Arg">pol</var> over <span class="SimpleMath">S</span>, the new field is constructed as polynomial extension of <span class="SimpleMath">S</span> with this polynomial; in this case, <var class="Arg">pol</var> is accessible as the value of <code class="func">DefiningPolynomial</code> (<a href="chap58.html#X7ADDCBF47E2ED3D4"><span class="RefLink">58.2-7</span></a>) for the new field, and a root of <var class="Arg">pol</var> in the new field is accessible as the value of <code class="func">RootOfDefiningPolynomial</code> (<a href="chap58.html#X8173DA4982DB1E8A"><span class="RefLink">58.2-8</span></a>).</p>

<p>Note that the subfield over which a field was constructed determines over which field the Galois group, conjugates, norm, trace, minimal polynomial, and trace polynomial are computed (see <code class="func">GaloisGroup</code> (<a href="chap58.html#X80CAA5BA82F09ED2"><span class="RefLink">58.3-1</span></a>), <code class="func">Conjugates</code> (<a href="chap58.html#X837A4A5781F8EE92"><span class="RefLink">58.3-6</span></a>), <code class="func">Norm</code> (<a href="chap58.html#X838515278587FF01"><span class="RefLink">58.3-4</span></a>), <code class="func">Trace</code> (<a href="chap58.html#X7DD17EB581200AD6"><span class="RefLink">58.3-5</span></a>), <code class="func">MinimalPolynomial</code> (<a href="chap58.html#X8738C6687D784BB5"><span class="RefLink">58.3-2</span></a>), <code class="func">TracePolynomial</code> (<a href="chap58.html#X80FE7E017C2D255C"><span class="RefLink">58.3-3</span></a>)).</p>

<p>The field is regarded as a vector space (see <a href="chap61.html#X7DAD6700787EC845"><span class="RefLink">61</span></a>) over the given subfield, so this determines the dimension and the canonical basis of the field.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f1:= GF( 2^4 );</span>
GF(2^4)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( GaloisGroup ( f1 ) );</span>
4
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">BasisVectors( Basis( f1 ) );</span>
[ Z(2)^0, Z(2^4), Z(2^4)^2, Z(2^4)^3 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f2:= GF( GF(4), 2 );</span>
AsField( GF(2^2), GF(2^4) )
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( GaloisGroup( f2 ) );</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">BasisVectors( Basis( f2 ) );</span>
[ Z(2)^0, Z(2^4) ]
</pre></div>

<p><a id="X788B1ECD83C70516" name="X788B1ECD83C70516"></a></p>

<h5>59.3-3 PrimitiveRoot</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PrimitiveRoot</code>( <var class="Arg">F</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<p>A <em>primitive root</em> of a finite field is a generator of its multiplicative group. A primitive root is always a primitive element (see <code class="func">PrimitiveElement</code> (<a href="chap58.html#X86DB31B57FB4F570"><span class="RefLink">58.2-3</span></a>)), the converse is in general not true.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f:= GF( 3^5 );</span>
GF(3^5)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveRoot( f );</span>
Z(3^5)
</pre></div>

<p><a id="X7A5F075185CE5B06" name="X7A5F075185CE5B06"></a></p>

<h4>59.4 <span class="Heading">Frobenius Automorphisms</span></h4>

<p><a id="X8758E4AB7D0A1955" name="X8758E4AB7D0A1955"></a></p>

<h5>59.4-1 FrobeniusAutomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; FrobeniusAutomorphism</code>( <var class="Arg">F</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
<p>returns the Frobenius automorphism of the finite field <var class="Arg">F</var> as a field homomorphism (see <a href="chap32.html#X7E88C32A82E942DA"><span class="RefLink">32.12</span></a>).</p>

<p>The <em>Frobenius automorphism</em> <span class="SimpleMath">f</span> of a finite field <span class="SimpleMath">F</span> of characteristic <span class="SimpleMath">p</span> is the function that takes each element <span class="SimpleMath">z</span> of <span class="SimpleMath">F</span> to its <span class="SimpleMath">p</span>-th power. Each field automorphism of <span class="SimpleMath">F</span> is a power of <span class="SimpleMath">f</span>. Thus <span class="SimpleMath">f</span> is a generator for the Galois group of <span class="SimpleMath">F</span> relative to the prime field of <span class="SimpleMath">F</span>, and an appropriate power of <span class="SimpleMath">f</span> is a generator of the Galois group of <span class="SimpleMath">F</span> over a subfield (see <code class="func">GaloisGroup</code> (<a href="chap58.html#X80CAA5BA82F09ED2"><span class="RefLink">58.3-1</span></a>)).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f := GF(16);</span>
GF(2^4)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x := FrobeniusAutomorphism( f );</span>
FrobeniusAutomorphism( GF(2^4) )
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(16) ^ x;</span>
Z(2^4)^2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x^2;</span>
FrobeniusAutomorphism( GF(2^4) )^2
</pre></div>

<p>The image of an element <span class="SimpleMath">z</span> under the <span class="SimpleMath">i</span>-th power of <span class="SimpleMath">f</span> is computed as the <span class="SimpleMath">p^i</span>-th power of <span class="SimpleMath">z</span>. The product of the <span class="SimpleMath">i</span>-th power and the <span class="SimpleMath">j</span>-th power of <span class="SimpleMath">f</span> is the <span class="SimpleMath">k</span>-th power of <span class="SimpleMath">f</span>, where <span class="SimpleMath">k</span> is <span class="SimpleMath">i j mod</span> <code class="code">Size(<var class="Arg">F</var>)</code><span class="SimpleMath">-1</span>. The zeroth power of <span class="SimpleMath">f</span> is <code class="code">IdentityMapping( <var class="Arg">F</var> )</code>.</p>

<p><a id="X869919BB7EBE5741" name="X869919BB7EBE5741"></a></p>

<h4>59.5 <span class="Heading">Conway Polynomials</span></h4>

<p><a id="X7C2425A786F09054" name="X7C2425A786F09054"></a></p>

<h5>59.5-1 ConwayPolynomial</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; ConwayPolynomial</code>( <var class="Arg">p</var>, <var class="Arg">n</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>is the Conway polynomial of the finite field <span class="SimpleMath">GF(p^n)</span> as polynomial over the prime field in characteristic <var class="Arg">p</var>.</p>

<p>The <em>Conway polynomial</em> <span class="SimpleMath">Φ_{n,p}</span> of <span class="SimpleMath">GF(p^n)</span> is defined by the following properties.</p>

<p>First define an ordering of polynomials of degree <span class="SimpleMath">n</span> over <span class="SimpleMath">GF(p)</span>, as follows. <span class="SimpleMath">f = ∑_{i = 0}^n (-1)^i f_i x^i</span> is smaller than <span class="SimpleMath">g = ∑_{i = 0}^n (-1)^i g_i x^i</span> if and only if there is an index <span class="SimpleMath">m ≤ n</span> such that <span class="SimpleMath">f_i = g_i</span> for all <span class="SimpleMath">i &gt; m</span>, and <span class="SimpleMath">tilde{f_m} &lt; tilde{g_m}</span>, where <span class="SimpleMath">tilde{c}</span> denotes the integer value in <span class="SimpleMath">{ 0, 1, ..., p-1 }</span> that is mapped to <span class="SimpleMath">c ∈ GF(p)</span> under the canonical epimorphism that maps the integers onto <span class="SimpleMath">GF(p)</span>.</p>

<p><span class="SimpleMath">Φ_{n,p}</span> is <em>primitive</em> over <span class="SimpleMath">GF(p)</span> (see <code class="func">IsPrimitivePolynomial</code> (<a href="chap66.html#X834B54947FAADEA4"><span class="RefLink">66.4-12</span></a>)). That is, <span class="SimpleMath">Φ_{n,p}</span> is irreducible, monic, and is the minimal polynomial of a primitive root of <span class="SimpleMath">GF(p^n)</span>.</p>

<p>For all divisors <span class="SimpleMath">d</span> of <span class="SimpleMath">n</span> the compatibility condition <span class="SimpleMath">Φ_{d,p}( x^{frac{p^n-1}{p^m-1}} ) ≡ 0 mod {Φ_{n,p}(x)}</span> holds. (That is, the appropriate power of a zero of <span class="SimpleMath">Φ_{n,p}</span> is a zero of the Conway polynomial <span class="SimpleMath">Φ_{d,p}</span>.)</p>

<p>With respect to the ordering defined above, <span class="SimpleMath">Φ_{n,p}</span> shall be minimal.</p>

<p>The computation of Conway polynomials can be time consuming. Therefore, <strong class="pkg">GAP</strong> comes with a list of precomputed polynomials. If a requested polynomial is not stored then <strong class="pkg">GAP</strong> prints a warning and computes it by checking all polynomials in the order defined above for the defining conditions. If <span class="SimpleMath">n</span> is not a prime this is probably a very long computation. (Some previously known polynomials with prime <span class="SimpleMath">n</span> are not stored in <strong class="pkg">GAP</strong> because they are quickly recomputed.) Use the function <code class="func">IsCheapConwayPolynomial</code> (<a href="chap59.html#X78A7C1247E129AD9"><span class="RefLink">59.5-2</span></a>) to check in advance if <code class="func">ConwayPolynomial</code> will give a result after a short time.</p>

<p>Note that primitivity of a polynomial can only be checked if <strong class="pkg">GAP</strong> can factorize <span class="SimpleMath">p^n-1</span>. A sufficiently new version of the <strong class="pkg">FactInt</strong> package contains many precomputed factors of such numbers from various factorization projects.</p>

<p>See <a href="chapBib.html#biBL03">[Lüb03]</a> for further information on known Conway polynomials.</p>

<p>An interactive overview of the Conway polynomials known to <strong class="pkg">GAP</strong> is provided by the function <code class="code">BrowseConwayPolynomials</code> from the <strong class="pkg">GAP</strong> package <strong class="pkg">Browse</strong>, see <code class="func">BrowseGapData</code> (<span class="RefLink">???</span>).</p>

<p>If <var class="Arg">pol</var> is a result returned by <code class="func">ConwayPolynomial</code> the command <code class="code">Print( InfoText( <var class="Arg">pol</var> ) );</code> will print some info on the origin of that particular polynomial.</p>

<p>For some purposes it may be enough to have any primitive polynomial for an extension of a finite field instead of the Conway polynomial, see <code class="func">RandomPrimitivePolynomial</code> (<a href="chap59.html#X7ECC593583E68A6C"><span class="RefLink">59.5-3</span></a>) below.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ConwayPolynomial( 2, 5 );  ConwayPolynomial( 3, 7 );</span>
x_1^5+x_1^2+Z(2)^0
x_1^7-x_1^2+Z(3)^0
</pre></div>

<p><a id="X78A7C1247E129AD9" name="X78A7C1247E129AD9"></a></p>

<h5>59.5-2 IsCheapConwayPolynomial</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsCheapConwayPolynomial</code>( <var class="Arg">p</var>, <var class="Arg">n</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>Returns <code class="keyw">true</code> if <code class="code">ConwayPolynomial( <var class="Arg">p</var>, <var class="Arg">n</var> )</code> will give a result in <em>reasonable</em> time. This is either the case when this polynomial is pre-computed, or if <var class="Arg">n</var> is a not too big prime.</p>

<p><a id="X7ECC593583E68A6C" name="X7ECC593583E68A6C"></a></p>

<h5>59.5-3 RandomPrimitivePolynomial</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; RandomPrimitivePolynomial</code>( <var class="Arg">F</var>, <var class="Arg">n</var>[, <var class="Arg">i</var>] )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
<p>For a finite field <var class="Arg">F</var> and a positive integer <var class="Arg">n</var> this function returns a primitive polynomial of degree <var class="Arg">n</var> over <var class="Arg">F</var>, that is a zero of this polynomial has maximal multiplicative order <span class="SimpleMath">|<var class="Arg">F</var>|^n-1</span>. If <var class="Arg">i</var> is given then the polynomial is written in variable number <var class="Arg">i</var> over <var class="Arg">F</var> (see <code class="func">Indeterminate</code> (<a href="chap66.html#X79D0380D7FA39F7D"><span class="RefLink">66.1-1</span></a>)), the default for <var class="Arg">i</var> is 1.</p>

<p>Alternatively, <var class="Arg">F</var> can be a prime power q, then <var class="Arg">F</var> = GF(q) is assumed. And <var class="Arg">i</var> can be a univariate polynomial over <var class="Arg">F</var>, then the result is a polynomial in the same variable.</p>

<p>This function can work for much larger fields than those for which Conway polynomials are available, of course <strong class="pkg">GAP</strong> must be able to factorize <span class="SimpleMath">|<var class="Arg">F</var>|^n-1</span>.</p>

<p><a id="X78EE3656879C3B88" name="X78EE3656879C3B88"></a></p>

<h4>59.6 <span class="Heading">Printing, Viewing and Displaying Finite Field Elements</span></h4>

<p><a id="X80DAAA5E7C79C94C" name="X80DAAA5E7C79C94C"></a></p>

<h5>59.6-1 ViewObj</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; ViewObj</code>( <var class="Arg">z</var> )</td><td class="tdright">(&nbsp;method&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PrintObj</code>( <var class="Arg">z</var> )</td><td class="tdright">(&nbsp;method&nbsp;)</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; Display</code>( <var class="Arg">z</var> )</td><td class="tdright">(&nbsp;method&nbsp;)</td></tr></table></div>
<p>Internal finite field elements are viewed, printed and displayed (see section <a href="chap6.html#X8074A8387C9DB9A8"><span class="RefLink">6.3</span></a> for the distinctions between these operations) as powers of the primitive root (except for the zero element, which is displayed as 0 times the primitive root). Thus:</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(2);</span>
Z(2)^0
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(5)+Z(5);</span>
Z(5)^2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(256);</span>
Z(2^8)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Zero(Z(125));</span>
0*Z(5)
</pre></div>

<p>Note also that each element is displayed as an element of the field it generates, and that the size of the field is printed as a power of the characteristic.</p>

<p>Elements of larger fields are printed as <strong class="pkg">GAP</strong> expressions which represent them as sums of low powers of the primitive root:</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Print( Z(3,20)^100, "\n" );</span>
2*Z(3,20)^2+Z(3,20)^4+Z(3,20)^6+Z(3,20)^7+2*Z(3,20)^9+2*Z(3,20)^10+2*Z\
(3,20)^12+2*Z(3,20)^15+2*Z(3,20)^17+Z(3,20)^18+Z(3,20)^19
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Print( Z(3,20)^((3^20-1)/(3^10-1)), "\n" );</span>
Z(3,20)^3+2*Z(3,20)^4+2*Z(3,20)^7+Z(3,20)^8+2*Z(3,20)^10+Z(3,20)^11+2*\
Z(3,20)^12+Z(3,20)^13+Z(3,20)^14+Z(3,20)^15+Z(3,20)^17+Z(3,20)^18+2*Z(\
3,20)^19
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(3,20)^((3^20-1)/(3^10-1)) = Z(3,10);</span>
true
</pre></div>

<p>Note from the second example above, that these elements are not always written over the smallest possible field before being output.</p>

<p>The <code class="func">ViewObj</code> and <code class="func">Display</code> methods for these large finite field elements use a slightly more compact, but mathematically equivalent representation. The primitive root is represented by <code class="code">z</code>; its <span class="SimpleMath">i</span>-th power by <code class="code">z</code><span class="SimpleMath">i</span> and <span class="SimpleMath">k</span> times this power by <span class="SimpleMath">k</span><code class="code">z</code><span class="SimpleMath">i</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(5,20)^100;</span>
z2+z4+4z5+2z6+z8+3z9+4z10+3z12+z13+2z14+4z16+3z17+2z18+2z19
</pre></div>

<p>This output format is always used for <code class="func">Display</code>. For <code class="func">ViewObj</code> it is used only if its length would not exceed the number of lines specified in the user preference <code class="code">ViewLength</code> (see <code class="func">SetUserPreference</code> (<a href="chap3.html#X7B0AD104839B6C3C"><span class="RefLink">3.2-3</span></a>). Longer output is replaced by <code class="code">&lt;&lt;an element of GF(<var class="Arg">p</var>, <var class="Arg">d</var>)&gt;&gt;</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(2,409)^100000;</span>
&lt;&lt;an element of GF(2, 409)&gt;&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Display(Z(2,409)^100000);</span>
z2+z3+z4+z5+z6+z7+z8+z10+z11+z13+z17+z19+z20+z29+z32+z34+z35+z37+z40+z\
45+z46+z48+z50+z52+z54+z55+z58+z59+z60+z66+z67+z68+z70+z74+z79+z80+z81\
+z82+z83+z86+z91+z93+z94+z95+z96+z98+z99+z100+z101+z102+z104+z106+z109\
+z110+z112+z114+z115+z118+z119+z123+z126+z127+z135+z138+z140+z142+z143\
+z146+z147+z154+z159+z161+z162+z168+z170+z171+z173+z174+z181+z182+z183\
+z186+z188+z189+z192+z193+z194+z195+z196+z199+z202+z204+z205+z207+z208\
+z209+z211+z212+z213+z214+z215+z216+z218+z219+z220+z222+z223+z229+z232\
+z235+z236+z237+z238+z240+z243+z244+z248+z250+z251+z256+z258+z262+z263\
+z268+z270+z271+z272+z274+z276+z282+z286+z288+z289+z294+z295+z299+z300\
+z301+z302+z303+z304+z305+z306+z307+z308+z309+z310+z312+z314+z315+z316\
+z320+z321+z322+z324+z325+z326+z327+z330+z332+z335+z337+z338+z341+z344\
+z348+z350+z352+z353+z356+z357+z358+z360+z362+z364+z366+z368+z372+z373\
+z374+z375+z378+z379+z380+z381+z383+z384+z386+z387+z390+z395+z401+z402\
+z406+z408
</pre></div>

<p>Finally note that elements of large prime fields are stored and displayed as residue class objects. So</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Z(65537);</span>
ZmodpZObj( 3, 65537 )
</pre></div>


<div class="chlinkprevnextbot">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap58.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap60.html">[Next Chapter]</a>&nbsp;  </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>