home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / finfield.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  19.8 KB  |  532 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  finfield.tex                GAP documentation            Martin Schoenert
  4. %%
  5. %A  @(#)$Id: finfield.tex,v 3.8 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %%  This file describes the operators and functions of finite field elements.
  10. %%
  11. %H  $Log: finfield.tex,v $
  12. %H  Revision 3.8  1993/02/19  10:48:42  gap
  13. %H  adjustments in line length and spelling
  14. %H
  15. %H  Revision 3.7  1993/02/10  10:30:19  felsch
  16. %H  more examples fixed
  17. %H
  18. %H  Revision 3.6  1993/02/02  12:44:55  felsch
  19. %H  long line fixed
  20. %H
  21. %H  Revision 3.5  1993/02/01  15:01:41  felsch
  22. %H  examples fixed
  23. %H
  24. %H  Revision 3.4  1992/04/07  10:06:55  martin
  25. %H  fixed some more typos
  26. %H
  27. %H  Revision 3.3  1992/04/02  21:06:23  martin
  28. %H  changed *domain functions* to *set theoretic functions*
  29. %H
  30. %H  Revision 3.2  1992/03/25  15:37:32  martin
  31. %H  added "FrobeniusAutomorphism"
  32. %H
  33. %H  Revision 3.1  1991/12/30  12:09:18  martin
  34. %H  revised everything for GAP 3.1 manual
  35. %H
  36. %H  Revision 3.0  1991/04/11  11:30:55  martin
  37. %H  Initial revision under RCS
  38. %H
  39. %%
  40. \Chapter{Finite Fields}%
  41. \index{field!finite}\index{galois field}\index{field!galois}
  42.  
  43. Finite fields comprise an important algebraic  domain.  The elements in a
  44. field  form   an   additive  group   and  the  nonzero  elements  form  a
  45. multiplicative  group.  For  every prime power $q$ there exists  a unique
  46. field of  size  $q$ up to isomorphism.  {\GAP} supports finite fields  of
  47. size at most $2^{16}$.
  48.  
  49. The first section in this chapter describes how you can enter elements of
  50. finite fields and how {\GAP} prints them (see "Finite Field Elements").
  51.  
  52. The  next sections describe  the  operations applicable to  finite  field
  53. elements (see "Comparisons of  Finite Field Elements" and "Operations for
  54. Finite Field Elements").
  55.  
  56. The next section describes the function that tests whether an object is a
  57. finite field element (see "IsFFE").
  58.  
  59. The  next sections describe   the functions  that give  basic information
  60. about finite field elements (see "CharFFE", "DegreeFFE", and "OrderFFE").
  61.  
  62. The next  sections  describe  the functions  that compute  various  other
  63. representations of finite field elements (see "IntFFE" and "LogFFE").
  64.  
  65. The next section  describes  the  function that constructs a finite field
  66. (see "GaloisField").
  67.  
  68. Finite  fields  are  domains,  thus  all  set  theoretic   functions  are
  69. applicable to them (see  chapter "Domains" and "Set Functions  for Finite
  70. Fields").
  71.  
  72. Finite  fields  are  of course  fields,  thus  all  field  functions  are
  73. applicable to them and to their elements (see chapter "Fields" and "Field
  74. Functions for Finite Fields").
  75.  
  76. All functions are in 'LIBNAME/\"finfield.g\"'.
  77.  
  78. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  79. \Section{Finite Field Elements}%
  80. \index{Z}
  81.  
  82. 'Z( <p>\^<d> )'
  83.  
  84. The function 'Z' returns  the designated generator of  the multiplicative
  85. group of the finite field with '<p>\^<d>' elements.  <p>  must be a prime
  86. and '<p>\^<d>' must be less than or equal to $2^{16} = 65536$.
  87.  
  88. The  root returned by 'Z' is  a generator of  the multiplicative group of
  89. the finite field with $p^d$ elements, which  is cyclic.  The order of the
  90. element is  of course $p^d-1$.  The $p^d-1$  different powers of the root
  91. are exactly the nonzero elements of the finite field.
  92.  
  93. Thus  all nonzero elements of the  finite field  with '<p>\^<d>' elements
  94. can  be entered  as 'Z(<p>\^<d>)\^<i>'.  Note that this is  also the form
  95. that {\GAP} uses to output those elements.
  96.  
  97. The additive neutral element  is '0\*Z(<p>)'.  It  is  different from the
  98. integer '0' in subtle ways.  First 'IsInt( 0\*Z(<p>)  )' (see "IsInt") is
  99. 'false' and 'IsFFE( 0\*Z(<p>) )'  (see "IsFFE") is  'true', whereas it is
  100. just the other way around for the integer 0.
  101.  
  102. The multiplicative neutral element is 'Z(<p>)\^0'.   It is different from
  103. the integer '1' in subtle ways.  First 'IsInt( Z(<p>)\^0 )' (see "IsInt")
  104. is 'false' and 'IsFFE( Z(<p>)\^0 )' (see  "IsFFE") is  'true', whereas it
  105. is just the  other  way around for   the  integer 1.  Also '1+1'  is '2',
  106. whereas, e.g., 'Z(2)\^0 + Z(2)\^0' is '0\*Z(2)'.
  107.  
  108. The  various  roots  returned  by  'Z'  for  finite  fields  of the  same
  109. characteristic  are  compatible  in  the  following  sense.  If the field
  110. $GF(p^n)$ is a  subfield of the  field  $GF(p^m)$, i.e., $n$ divides $m$,
  111. then $Z(p^n) = Z(p^m)^{(p^m-1)/(p^n-1)}$.  Note that this is the simplest
  112. relation that may  hold  between a generator of $GF(p^n)$ and  $GF(p^m)$,
  113. since $Z(p^n)$ is an element of order $p^m-1$ and $Z(p^m)$  is an element
  114. of order  $p^n-1$.  This is achieved  by choosing $Z(p)$ as  the smallest
  115. primitive  root modulo $p$  and  $Z(p^n)$ as a root of the $n$-th  Conway
  116. polynomial of  characteristic $p$.   Those polynomials  where  defined by
  117. J.H.~Conway and computed by R.A.~Parker.
  118.  
  119. |    gap> z := Z(16);
  120.     Z(2^4)
  121.     gap> z*z;
  122.     Z(2^4)^2 |
  123.  
  124. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  125. \Section{Comparisons of Finite Field Elements}%
  126. \index{comparisons!of finite field elements}
  127.  
  128. '<z1> = <z2>'\\
  129. '<z1> \<> <z2>'
  130.  
  131. The equality  operator  '=' evaluates to 'true'  if the two elements in a
  132. finite  field <z1> and   <z2> are equal   and to 'false' otherwise.   The
  133. inequality operator '\<>' evaluates to  'true' if  the two  elements in a
  134. finite finite field <z1> and <z2> are not equal and to 'false' otherwise.
  135.  
  136. Note that the integer  0 is not equal to  the  zero element in any finite
  137. field.  There comparisons '<z> = 0' will always evaluate to 'false'.  Use
  138. '<z> = 0\*<z>' instead, or even better '<z> = <F>.zero', where <F> is the
  139. field record for a finite field of the same characteristic.
  140.  
  141. |    gap> Z(2^4)^10 = Z(2^4)^25;
  142.     true    # 'Z(2\^4)' has order 15
  143.     gap> Z(2^4)^10 = Z(2^2)^2;
  144.     true    # shows the embedding of 'GF(4)' into 'GF(16)'
  145.     gap> Z(2^4)^10 = Z(3);
  146.     false |
  147.  
  148. '<z1> \<\ <z2>'\\
  149. '<z1> \<= <z2>'\\
  150. '<z1>  >  <z2>'\\
  151. '<z1>  >= <z2>'
  152.  
  153. The operators  '\<',  '\<=', '>',  and  '=>' evaluate to  'true'  if  the
  154. element  in  a finite field <z1>  is  less  than, less than or equal  to,
  155. greater than, and greater than or equal to the element  in a finite field
  156. <z2>.
  157.  
  158. Elements in finite fields  are ordered as follows.   If the two  elements
  159. lie in fields of different characteristics the one that lies in the field
  160. with the  smaller characteristic is smaller.  If  the two elements lie in
  161. different fields  of  the same characteristic  the  one that  lies in the
  162. smaller field is smaller.  If the two elements lie  in the same field and
  163. one is  the zero and the  other is not, the zero  element is smaller.  If
  164. the  two elements lie  in  the same field and   both are nonzero, and are
  165. represented as $Z(p^d)^{i_1}$  and $Z(p^d)^{i_2}$ respectively, then  the
  166. one with the smaller $i$ is smaller.
  167.  
  168. You can  compare elements in a  finite field with objects of other types.
  169. Integers, rationals, and  cyclotomics are smaller than elements in finite
  170. fields, all other objects are larger.  Note especially that the integer 0
  171. is smaller than the zero in every finite field.
  172.  
  173. |    gap> Z(2) < Z(3);
  174.     true
  175.     gap> Z(2) < Z(4);
  176.     true
  177.     gap> 0*Z(2) < Z(2);
  178.     true
  179.     gap> Z(4) < Z(4)^2;
  180.     true
  181.     gap> 0 < 0*Z(2);
  182.     true
  183.     gap> Z(4) < [ Z(4) ];
  184.     true |
  185.  
  186. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  187. \Section{Operations for Finite Field Elements}%
  188.  
  189. '<z1>  +  <z2>'\\
  190. '<z1>  -  <z2>'\\
  191. '<z1> \*\ <z2>'\\
  192. '<z1>  /  <z2>'
  193.  
  194. The  operators '+', '-',  '\*' and '/' evaluate to  the sum,  difference,
  195. product,  and quotient of the two  finite field elements  <z1> and  <z2>,
  196. which  must lie in fields  of the same characteristic.  For  the quotient
  197. '/' <z2> must of course be nonzero.  The result  must of course lie  in a
  198. finite field of size less than  or equal to  $2^{16}$, otherwise an error
  199. is signalled.
  200.  
  201. Either operand may also be an integer <i>.  If <i> is zero it is taken as
  202. the  zero  in the finite  field, i.e.,  '<F>.zero', where  <F> is a field
  203. record for the finite  field in which the other  operand lies.  If <i> is
  204. positive, it is  taken as <i>-fold  sum '<F>.one+<F>.one+..+<F>.one'.  If
  205. <i> is negative it is taken as the additive inverse of '-<i>'.
  206.  
  207. |    gap> Z(8) + Z(8)^4;
  208.     Z(2^3)^2
  209.     gap> Z(8) - 1;
  210.     Z(2^3)^3
  211.     gap> Z(8) * Z(8)^6;
  212.     Z(2)^0
  213.     gap> Z(8) / Z(8)^6;
  214.     Z(2^3)^2
  215.     gap> -Z(9);
  216.     Z(3^2)^5 |
  217.  
  218. '<z> \^\ <i>'
  219.  
  220. The powering operator '\^' returns the <i>-th power of the  element  in a
  221. finite field <z>.  <i> must be an integer.  If  the exponent <i> is zero,
  222. '<z>\^<i>' is  defined as the one  in the finite  field,  even if  <z> is
  223. zero; if <i> is positive, '<z>\^<i>' is  defined as the  <i>-fold product
  224. '<z>\*<z>\*..\*<z>'; finally, if  <i> is negative, '<z>\^<i>' is  defined
  225. as '(1/<z>)\^-<i>'.  In this case <z> must of course be nonzero.
  226.  
  227. |    gap> Z(4)^2;
  228.     Z(2^2)^2
  229.     gap> Z(4)^3;
  230.     Z(2)^0    # is in fact 1
  231.     gap> (0*Z(4))^0;
  232.     Z(2)^0 |
  233.  
  234. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  235. \Section{IsFFE}%
  236. \index{test!for a finite field element}
  237.  
  238. 'IsFFE( <obj> )'
  239.  
  240. 'IsFFE' returns 'true' if <obj>, which may be  an object  of an arbitrary
  241. type, is an element in a finite field and 'false' otherwise.  Will signal
  242. an error if <obj> is an unbound variable.
  243.  
  244. Note that integers,  even though they can  be multiplied with elements in
  245. finite fields, are not  considered themselves elements in  finite fields.
  246. Therefore 'IsFFE' will return 'false' for integer arguments.
  247.  
  248. |    gap> IsFFE( Z(2^4)^7 );
  249.     true
  250.     gap> IsFFE( 5 );
  251.     false |
  252.  
  253. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  254. \Section{CharFFE}%
  255. \index{characteristic!of a finite field element}
  256.  
  257. 'CharFFE( <z> )' or 'CharFFE( <vec> )' or 'CharFFE( <mat> )'
  258.  
  259. 'CharFFE' returns the characteristic  of the finite  field <F> containing
  260. the  element <z>, respectively  all  elements of the  vector <vec> over a
  261. finite field (see "Vectors"), or matrix  <mat> over  a  finite field (see
  262. "Matrices").
  263.  
  264. |    gap> CharFFE( Z(16)^7 );
  265.     2
  266.     gap> CharFFE( Z(16)^5 );
  267.     2
  268.     gap> CharFFE( [ Z(3), Z(27)^11, Z(9)^3 ] );
  269.     3
  270.     gap> CharFFE( [ [ Z(5), Z(125)^3 ], [ Z(625)^13, Z(5) ] ] );
  271.     Error, CharFFE: <z> must be a finite field element, vector, or matrix
  272.     # The smallest finite field which contains all four of these elements
  273.     # is too large for {\GAP} |
  274.  
  275. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  276. \Section{DegreeFFE}%
  277. \index{degree!of a finite field element}
  278.  
  279. 'DegreeFFE( <z> )' or 'DegreeFFE( <vec> )' or 'DegreeFFE( <mat> )'
  280.  
  281. 'DegreeFFE'  returns  the   degree of  the   smallest  finite field   <F>
  282. containing the element <z>, respectively all elements of the vector <vec>
  283. over a finite field (see "Vectors"), or matrix  <mat> over a finite field
  284. (see "Matrices").  For vectors and matrices, an error is signalled if the
  285. smallest finite field containing all elements of the vector or matrix has
  286. size larger than $2^{16}$.
  287.  
  288. |    gap> DegreeFFE( Z(16)^7 );
  289.     4
  290.     gap> DegreeFFE( Z(16)^5 );
  291.     2
  292.     gap> DegreeFFE( [ Z(3), Z(27)^11, Z(9)^3 ] );
  293.     6
  294.     gap> DegreeFFE( [ [ Z(5), Z(125)^3 ], [ Z(625)^13, Z(5) ] ] );
  295.     Error, DegreeFFE: <z> must be a finite field element, vector, or matrix
  296.     # The smallest finite field which contains all four of these elements
  297.     # is too large for {\GAP} |
  298.  
  299. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  300. \Section{OrderFFE}%
  301. \index{order!of a finite field element}
  302.  
  303. 'OrderFFE( <z> )'
  304.  
  305. 'OrderFFE' returns the order of  the element <z> in  a finite field.  The
  306. order  is the smallest positive integer <i> such  that  '<z>\^<i>'  is 1.
  307. The order of the zero in a finite field is defined to be 0.
  308.  
  309. |    gap> OrderFFE( Z(16)^7 );
  310.     15
  311.     gap> OrderFFE( Z(16)^5 );
  312.     3
  313.     gap> OrderFFE( Z(27)^11 );
  314.     26
  315.     gap> OrderFFE( Z(625)^13 );
  316.     48
  317.     gap> OrderFFE( Z(211)^0 );
  318.     1 |
  319.  
  320. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  321. \Section{IntFFE}
  322. \index{convert!a finite field element to an integer}
  323.  
  324. 'IntFFE( <z> )'
  325.  
  326. 'IntFFE' returns the integer corresponding to the element <z>, which must
  327. lie in  a finite  prime field.   That is  'IntFFE' returns  the  smallest
  328. nonnegative integer <i> such that '<i> \*\ <z>\^ 0 = <z>'.
  329.  
  330. The  correspondence between   elements   from a finite   prime field   of
  331. characteristic <p> and the integers between 0  and  '<p>-1' is defined by
  332. choosing 'Z(<p>)'  the     smallest  primitive  root    mod   <p>    (see
  333. "PrimitiveRootMod").
  334.  
  335. |    gap> IntFFE( Z(13) );
  336.     2
  337.     gap> PrimitiveRootMod( 13 );
  338.     2
  339.     gap> IntFFE( Z(409) );
  340.     21
  341.     gap> IntFFE( Z(409)^116 );
  342.     311
  343.     gap> 21^116 mod 409;
  344.     311 |
  345.  
  346. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  347. \Section{LogFFE}
  348. \index{logarithm!of a finite field element, discrete}
  349. \index{discrete logarithm!of a finite field element}
  350.  
  351. 'LogFFE( <z> )' \\
  352. 'LogFFE( <z>, <r> )'
  353.  
  354. In the first form 'LogFFE' returns  the discrete logarithm of the element
  355. <z> in a finite field with respect to the  root 'FieldFFE(<z>).root'.  An
  356. error is signalled if <z> is zero.
  357.  
  358. In the second form 'LogFFE' returns the discrete logarithm of the element
  359. <z> in  a  finite  field with  respect  to  the  root <r>.   An  error is
  360. signalled if <z> is zero, or if <z> is not a power of <r>.
  361.  
  362. The *discrete logarithm* of an element $z$ with  respect to a root $r$ is
  363. the smallest nonnegative integer $i$ such that $r^i = z$.
  364.  
  365. |    gap> LogFFE( Z(409)^116 );
  366.     116
  367.     gap> LogFFE( Z(409)^116, Z(409)^2 );
  368.     58 |
  369.  
  370. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  371. \Section{GaloisField}%
  372. \index{GF}
  373.  
  374. 'GaloisField( <p>\^<d> )' \\
  375. 'GF( <p>\^<d> )' \\
  376. 'GaloisField( <p>\|<S>, <d>\|<pol>\|<bas> )' \\
  377. 'GF( <p>\|<S>, <d>\|<pol>\|<bas> )'
  378.  
  379. 'GaloisField' returns a  field record (see  "Field Records") for a finite
  380. field.  It takes two arguments.  The form  'GaloisField(<p>,<d>)',  where
  381. <p>,<d> are integers, can also be given as 'GaloisField(<p>\^<d>)'.  'GF'
  382. is an abbreviation for 'GaloisField'.
  383.  
  384. The first argument  specifies the subfield <S>  over which the new  field
  385. <F> is to be taken.  It can be  a prime or  a finite field record.  If it
  386. is a prime <p>, the  subfield is the  prime field of this characteristic.
  387. If it is a field record <S>, the subfield is the  field described by this
  388. record.
  389.  
  390. The  second  argument specifies the extension.  It can be an integer,  an
  391. irreducible polynomial, or a base.   If  it is an  integer  <d>, the  new
  392. field  is  constructed  as  the  polynomial  extension  with  the  Conway
  393. polynomial  of degree <d> over the subfield <S>.  If it is an irreducible
  394. polynomial <pol>,  in which case the elements  of the list <pol> must all
  395. lie  in  the  subfield <S>, the new field  is  constructed as  polynomial
  396. extension  of the  subfield <S> with  this  polynomial.  If  it is a base
  397. <bas>,  in which  case  the elements  of  the list <bas>  must be  linear
  398. independently  over the  subfield  <S>,  the  new field is constructed as
  399. a linear vector space over the subfield <S>.
  400.  
  401. Note that the subfield over which a field was constructed determines over
  402. which field the Galois group, conjugates, norm,  trace,  minimal polynom,
  403. and characteristic polynom are computed (see "GaloisGroup", "Conjugates",
  404. "Norm", "Trace", "MinPol", "CharPol", and   "Field  Functions for  Finite
  405. Fields").
  406.  
  407. |    gap> GF( 2^4 );
  408.     GF(2^4)
  409.     gap> GF( GF(2^4), 2 );
  410.     GF(2^8)/GF(2^4) |
  411.  
  412. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  413. \Section{FrobeniusAutomorphism}%
  414. \index{homomorphisms!Frobenius, field}%
  415. \index{field homomorphisms!Frobenius}%
  416. \index{Image!for Frobenius automorphisms}%
  417. \index{CompositionMapping!for Frobenius automorphisms}
  418.  
  419. 'FrobeniusAutomorphism( <F> )'
  420.  
  421. 'FrobeniusAutomorphism'  returns the Frobenius automorphism of the finite
  422. field <F> as a field homomorphism (see "Field Homomorphisms").
  423.  
  424. The  Frobenius automorphism $f$ of  a finite field $F$  of characteristic
  425. $p$  is  the function that  takes  each element $z$ of  $F$ to its $p$-th
  426. power.    Each  automorphism  of  $F$  is  a   power   of  the  Frobenius
  427. automorphism.  Thus the  Frobenius  automorphism  is a generator  for the
  428. Galois group of $F$ (and an appropriate power of it is a generator of the
  429. Galois group of $F$ over a subfield $S$) (see "GaloisGroup").
  430.  
  431. |    gap> f := GF(16);
  432.     GF(2^4)
  433.     gap> x := FrobeniusAutomorphism( f );
  434.     FrobeniusAutomorphism( GF(2^4) )
  435.     gap> Z(16) ^ x;
  436.     Z(2^4)^2 |
  437.  
  438. The image  of an  element  <z> under the  <i>-th  power  of the Frobenius
  439. automorphism  <f> of a finite field  <F> of characteristic <p> is  simply
  440. computed by computing the '<p>\^<i>'-th power of <z>.  The product of the
  441. <i>-th power and the <j>-th  power of <f> is  the  <k>-th power  of  <f>,
  442. where <k> is  '<i>\*<j> mod (Size(<F>)-1)'.   The zeroth  power of <f> is
  443. printed as 'IdentityMapping( <F> )'.
  444.  
  445. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  446. \Section{Set Functions for Finite Fields}%
  447. \index{Elements!for finite fields}%
  448. \index{in!for finite fields}\index{membership test!for finite fields}%
  449. \index{Random!for finite fields}
  450. \index{Intersection!for finite fields}
  451.  
  452. Finite  fields are of course domains.  Thus all  set theoretic  functions
  453. are  applicable  to finite fields (see chapter "Domains").   This section
  454. gives  further  comments on the definitions and  implementations of those
  455. functions for finite fields.  All  set theoretic  functions not mentioned
  456. here are not treated specially for finite fields.
  457.  
  458. 'Elements'
  459.  
  460. The elements  of a  finite field  are computed  using the  fact that  the
  461. finite field is a vector space over its prime field.
  462.  
  463. 'in'
  464.  
  465. The membership test is  of course  very simple,  we  just  have  to  test
  466. whether the  element is a  finite field element with 'IsFFE',  whether it
  467. has the  correct characteristic  with 'CharFFE', and  whether its  degree
  468. divides  the  degree of the  finite field  with 'DegreeFFE' (see "IsFFE",
  469. "CharFFE", and "DegreeFFE").
  470.  
  471. 'Random'
  472.  
  473. A random element of $GF(p^n)$ is  computed by  computing a random integer
  474. $i$  from  $[0..p^n-1]$    and returning  $0\*Z(p)$  if  $i   = 0$    and
  475. $Z(p^n)^{i-1}$ otherwise.
  476.  
  477. 'Intersection'
  478.  
  479. The  intersection  of  $GF(p^n)$  and  $GF(p^m)$   is the   finite  field
  480. $GF(p^{Gcd(n,m)})$, and is returned as finite field record.
  481.  
  482. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  483. \Section{Field Functions for Finite Fields}%
  484. \index{GaloisGroup!for finite fields}%
  485. \index{Conjugates!for finite fields}%
  486. \index{Norm!for finite fields}
  487.  
  488. Finite fields  are, as the name  already implies, fields.  Thus all field
  489. functions are applicable to finite fields and their elements (see chapter
  490. "Fields").  This section  gives further comments on  the  definitions and
  491. implementations  of  those  functions  for   finite fields.   All  domain
  492. functions not mentioned here are not treated specially for finite fields.
  493.  
  494. 'Field' and 'DefaultField'
  495.  
  496. Both  'Field'   and 'DefaultField'  return  the   smallest   finite field
  497. containing the arguments as  an extension of  the  prime field.
  498.  
  499. 'GaloisGroup'
  500.  
  501. The Galois  group of a finite field $F$ of size $p^m$ over a subfield $S$
  502. of size $q =  p^n$ is a cyclic  group of  size $m/n$.  It is generated by
  503. the  *Frobenius automorphism*  that takes every  element of  $F$  to  its
  504. $q$-th power.  This automorphism of  $F$  leaves exactly the subfield $S$
  505. fixed.
  506.  
  507. 'Conjugates'
  508.  
  509. According  to the above theorem about  the Galois  group, each element of
  510. $F$ has  $m/n$ conjugates, $z,  z^q,  z^{q^2}, ..., z^{q^{m/n-1}}$.
  511.  
  512. 'Norm'
  513.  
  514. The  norm is the  product of the conjugates, i.e., $z^{{p^m-1}/{p^n-1}}$.
  515. Because  we  have $Z(p^n) =  Z(p^m)^{{p^m-1}/{p^n-1}}$, it  follows  that
  516. $Norm( GF(p^m)/GF(p^n), Z(p^m)^i ) = Z(p^n)^i$.
  517.  
  518. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  519. %%
  520. %E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
  521. %%
  522. %%  Local Variables:
  523. %%  mode:               outline
  524. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section"
  525. %%  fill-column:        73
  526. %%  eval:               (hide-body)
  527. %%  End:
  528. %%
  529.  
  530.  
  531.  
  532.