/usr/share/gap/doc/ref/chap59.html is in gap-doc 4r6p5-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"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap58.html">[Previous Chapter]</a> <a href="chap60.html">[Next Chapter]</a> </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"> </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"> </span><a href="chap59.html#X7D3DF32C84FEBD25">59.1-1 IsFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X7AA52FAF7EDEDD56">59.1-2 Z</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X8612BCEA816CF1B9">59.1-3 IsLexOrderedFFE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap59.html#X828E846E7C1EA3DD">59.2-1 DegreeFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X7B049A3478B369E4">59.2-2 LogFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X79F48E337FC2746A">59.2-3 IntFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X7DABD827848BCC2A">59.2-4 IntFFESymm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X8009968782F18888">59.2-5 IntVecFFE</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X807959EE82CED148">59.2-6 AsInternalFFE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap59.html#X7979F51D7C43AB05">59.3-1 DefaultField</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X8592DBB086A8A9BE">59.3-2 GaloisField</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X788B1ECD83C70516">59.3-3 PrimitiveRoot</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap59.html#X8758E4AB7D0A1955">59.4-1 FrobeniusAutomorphism</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap59.html#X7C2425A786F09054">59.5-1 ConwayPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X78A7C1247E129AD9">59.5-2 IsCheapConwayPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap59.html#X7ECC593583E68A6C">59.5-3 RandomPrimitivePolynomial</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </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">‣ IsFFE</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFFECollection</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFFECollColl</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFFECollCollColl</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</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">‣ Z</code>( <var class="Arg">p^d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Z</code>( <var class="Arg">p</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</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"><= 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">> 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></span> <span class="GAPinput">a:= Z( 32 );</span>
Z(2^5)
<span class="GAPprompt">gap></span> <span class="GAPinput">a+a;</span>
0*Z(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">a*a;</span>
Z(2^5)^2
<span class="GAPprompt">gap></span> <span class="GAPinput">b := Z(3,12);</span>
z
<span class="GAPprompt">gap></span> <span class="GAPinput">b*b;</span>
z2
<span class="GAPprompt">gap></span> <span class="GAPinput">b+b;</span>
2z
<span class="GAPprompt">gap></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></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
<function>( <arguments> ) 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></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">‣ IsLexOrderedFFE</code>( <var class="Arg">ffe</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLogOrderedFFE</code>( <var class="Arg">ffe</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Elements of finite fields can be compared using the operators <code class="code">=</code> and <code class="code"><</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> < <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">\<</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></span> <span class="GAPinput">Z( 16 )^10 = Z( 4 )^2; # illustrates embedding of GF(4) in GF(16)</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">0 < 0*Z(101);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Z(256) > Z(101);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Z(2,20) < 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></span> <span class="GAPinput">Characteristic( Z( 16 )^10 ); Characteristic( Z( 9 )^2 );</span>
2
3
<span class="GAPprompt">gap></span> <span class="GAPinput">Characteristic( [ Z(4), Z(8) ] );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">One( Z(9) ); One( 0*Z(4) );</span>
Z(3)^0
Z(2)^0
<span class="GAPprompt">gap></span> <span class="GAPinput">Inverse( Z(9) ); AdditiveInverse( Z(9) );</span>
Z(3^2)^7
Z(3^2)^5
<span class="GAPprompt">gap></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">‣ DegreeFFE</code>( <var class="Arg">z</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DegreeFFE</code>( <var class="Arg">vec</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DegreeFFE</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</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></span> <span class="GAPinput">DegreeFFE( Z( 16 )^10 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">DegreeFFE( Z( 16 )^11 );</span>
4
<span class="GAPprompt">gap></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">‣ LogFFE</code>( <var class="Arg">z</var>, <var class="Arg">r</var> )</td><td class="tdright">( operation )</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></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">‣ IntFFE</code>( <var class="Arg">z</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Int</code>( <var class="Arg">z</var> )</td><td class="tdright">( method )</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 < 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></span> <span class="GAPinput">IntFFE( Z(13) ); PrimitiveRootMod( 13 );</span>
2
2
<span class="GAPprompt">gap></span> <span class="GAPinput">IntFFE( Z(409) );</span>
21
<span class="GAPprompt">gap></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">‣ IntFFESymm</code>( <var class="Arg">z</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IntFFESymm</code>( <var class="Arg">vec</var> )</td><td class="tdright">( attribute )</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 < 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></span> <span class="GAPinput">IntFFE(Z(13)^2);IntFFE(Z(13)^3);</span>
4
8
<span class="GAPprompt">gap></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">‣ IntVecFFE</code>( <var class="Arg">vecffe</var> )</td><td class="tdright">( operation )</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">‣ AsInternalFFE</code>( <var class="Arg">ffe</var> )</td><td class="tdright">( attribute )</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">‣ DefaultField</code>( <var class="Arg">list</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DefaultRing</code>( <var class="Arg">list</var> )</td><td class="tdright">( method )</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></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">‣ GaloisField</code>( <var class="Arg">p^d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GF</code>( <var class="Arg">p^d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GaloisField</code>( <var class="Arg">p</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GF</code>( <var class="Arg">p</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GaloisField</code>( <var class="Arg">subfield</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GF</code>( <var class="Arg">subfield</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GaloisField</code>( <var class="Arg">p</var>, <var class="Arg">pol</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GF</code>( <var class="Arg">p</var>, <var class="Arg">pol</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GaloisField</code>( <var class="Arg">subfield</var>, <var class="Arg">pol</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GF</code>( <var class="Arg">subfield</var>, <var class="Arg">pol</var> )</td><td class="tdright">( function )</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></span> <span class="GAPinput">f1:= GF( 2^4 );</span>
GF(2^4)
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( GaloisGroup ( f1 ) );</span>
4
<span class="GAPprompt">gap></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></span> <span class="GAPinput">f2:= GF( GF(4), 2 );</span>
AsField( GF(2^2), GF(2^4) )
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( GaloisGroup( f2 ) );</span>
2
<span class="GAPprompt">gap></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">‣ PrimitiveRoot</code>( <var class="Arg">F</var> )</td><td class="tdright">( attribute )</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></span> <span class="GAPinput">f:= GF( 3^5 );</span>
GF(3^5)
<span class="GAPprompt">gap></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">‣ FrobeniusAutomorphism</code>( <var class="Arg">F</var> )</td><td class="tdright">( attribute )</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></span> <span class="GAPinput">f := GF(16);</span>
GF(2^4)
<span class="GAPprompt">gap></span> <span class="GAPinput">x := FrobeniusAutomorphism( f );</span>
FrobeniusAutomorphism( GF(2^4) )
<span class="GAPprompt">gap></span> <span class="GAPinput">Z(16) ^ x;</span>
Z(2^4)^2
<span class="GAPprompt">gap></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">‣ ConwayPolynomial</code>( <var class="Arg">p</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</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 > m</span>, and <span class="SimpleMath">tilde{f_m} < 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></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">‣ IsCheapConwayPolynomial</code>( <var class="Arg">p</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</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">‣ RandomPrimitivePolynomial</code>( <var class="Arg">F</var>, <var class="Arg">n</var>[, <var class="Arg">i</var>] )</td><td class="tdright">( function )</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">‣ ViewObj</code>( <var class="Arg">z</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrintObj</code>( <var class="Arg">z</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Display</code>( <var class="Arg">z</var> )</td><td class="tdright">( method )</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></span> <span class="GAPinput">Z(2);</span>
Z(2)^0
<span class="GAPprompt">gap></span> <span class="GAPinput">Z(5)+Z(5);</span>
Z(5)^2
<span class="GAPprompt">gap></span> <span class="GAPinput">Z(256);</span>
Z(2^8)
<span class="GAPprompt">gap></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></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></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></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></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 <code class="code">ViewLength()</code> lines. Longer output is replaced by <code class="code"><<an element of GF(<var class="Arg">p</var>, <var class="Arg">d</var>)>></code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Z(2,409)^100000;</span>
<<an element of GF(2, 409)>>
<span class="GAPprompt">gap></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></span> <span class="GAPinput">Z(65537);</span>
ZmodpZObj( 3, 65537 )
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap58.html">[Previous Chapter]</a> <a href="chap60.html">[Next Chapter]</a> </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>
|