$ENTRY Go { =
* x^2 + x + 1 -- irreducible polinomial .
* To inverse x + 1 .
  <Prout  <F8_Int  Inv ( '111' ) ' = 11' >>

* x^3 + x + 1 -- irreducible polinomial .
* To add x^2 + x + 1  and x^2 + x .
  <Prout  <F8_Int  Add ( '1011' )  ( '111' ) ' = 110' >>

* x^3 + x + 1 -- irreducible polinomial .
* To multiply x^2 + x + 1  and x^2 + x .
  <Prout  <F8_Int  Mul ( '1011' )  ( '111' ) ' = 11'  >> ;
} /*  For testing. */



*   Arithmetic of a finite field. Charachter = 2.
*   e.PX - polinomial irreducible over the field Z_2 (from 2 elements),
*   e.1 - arguments
*   e.PX and e1 are encoded with a sequence of '0' and '1'
*   Examples: '101' == x^2 + 1
*             '1011' == x^3 + x + 1
*      /* empty */   == 0
*
F8_Int   { s.Oper ( e.PX ) e.1 = <BR 'PX=' e.PX >
                                 <F8_Int1 s.Oper e.1 > ; }
F8_Int1  {
         Add (e.1) e.2 = <F8_Add (e.1) e.2>;
         Sub (e.1) e.2 = <F8_Add (e.1) e.2>;
         Mul (e.1) e.2 = <F8_Mul (e.1) e.2>;
         Div (e.1) e.2 = <F8_Div (e.1) e.2>;
         Inv e.1       = <F8_Inv e.1>;
         }    

* addition of polinomals over a field from two elements.
* subtraction is equal to addition.
$ENTRY Z2X_Add  {  (e.1) e.2 = <Delete_0 <Z2X_Add1  (e.1) e.2>>;  }

Z2X_Add1  {
          (e.1 s.A) e.2 s.A = <Z2X_Add1 (e.1) e.2> '0' ;
          (e.1 s.A) e.2 s.B = <Z2X_Add1 (e.1) e.2> '1' ;
          (e.1)     e.2     = e.1 e.2 ;
          }

* delete zeros from front of a polinomal.
Delete_0  {
          '0' e.2 = <Delete_0 e.2 >;
          '1' e.2 = '1' e.2;
              e.1 =  ;
          }

* Multiplication of polinomals over a field from two elements.
* "School-multiplication with a column".
$ENTRY Z2X_Mul  {
         (e.1)         = ;
         (  )      e.2 = ;
         (e.1) s.A e.2 = <Z2X_Mul1 (e.1) (e.1) e.2 >;
         }

Z2X_Mul1  {
      (e.1) (e.2)         = e.1;
      (e.1) (e.2) '0' e.3 = <Z2X_Mul1 (e.1 '0' ) (e.2) e.3 >;
      (e.1) (e.2) '1' e.3 = <Z2X_Mul1 (<Z2X_Add (e.1 '0' ) e.2>)(e.2)e.3>;
          }

* Euclid's division of polinomals over a field from two elements.
* "School-division with a column".
* <Z2X_div  (e.a) e.b > ==> e.q (e.rest)
$ENTRY Z2X_Div  {
         (   ) e.1 = ( );
         (e.1) e.2 = <Z2X_Div1 ( ) (e.1) ( ) e.2>;
         }

Z2X_Div1  {
  (e.1) (s.A e.2) (e.3) s.B e.4 = <Z2X_Div1 (e.1 s.A)(e.2)(e.3 s.B)e.4>;
  (e.1) ( )       (e.3) s.B e.4 = (e.1);
  (e.1) (e.2)     (e.3)         = <Z2X_Div2 (e.1) (e.2) (e.3)>;
          }

Z2X_Div2  {
  ('1'e.1)(e.2)(e.3) = '1' <Z2X_Div3 (<Z2X_Add1 ('1'e.1)e.3>)(e.2)(e.3)>;
  ('0'e.1)(e.2)(e.3) = '0' <Z2X_Div3 ('0' e.1)(e.2)(e.3) >;
          }

Z2X_Div3  {
       ('0'e.1) ( )    (e.3) = (<Delete_0 e.1>);
       ('0'e.1) (s.B e.2)(e.3) = <Z2X_Div2 (e.1 s.B) (e.2) (e.3) >;
          }

* addition over a field with characteristic 2.
$ENTRY F8_Add  {  (e1) e2 = <Z2X_Add (e1) e2>;  }

* Multiplication over a fieed with characteristic 2.
$ENTRY F8_Mul  {  (e.1) e.2 = <Mod_PX <Z2X_Mul (e.1) e.2>>; }

Mod_PX    {  e.1, <CP 'PX' >: e.P = <Mod_PX1 <Z2X_Div (e.1) e.P >>; }
Mod_PX1   {  e.Q (e.R) = e.R; }

* Division over a field with characteristic 2.
$ENTRY F8_Div    {  (e.1) e.2 = <F8_Mul (e.1) <F8_Inv  e.2 >>; }

* Inversing in a field with characteristic 2.
* Euclid's algorithm: GCD(M,p) = U*M + V*p
*                           1  = U*M
*                           U  = M^(-1)  
/*
  Note: A = X*M (mod p)
        B = Y*M (mod p)
   and  A = Q*B + R,
  then  R = (X-Y*Q)*M (mod p)
  We start with p = 0*M (mod p)
                M = 1*M (mod p)
*/
$ENTRY F8_Inv  {
         e.m, <CP 'PX' >: e.P = <F8_Inv1  ( e.P ) ( ) (e.m) ( '1' ) >;
        }

F8_Inv1  {
        (e.A) (e.X) ('1') (e.Y) = e.Y;
        (e.A) (e.X) (e.B) (e.Y) = <F8_Inv1 (e.B) (e.Y)
                         <F8_Inv2 (e.X) (e.Y) <Z2X_Div (e.A) e.B>>>;
         }

F8_Inv2  {
   (e.X) (e.Y) e.Q (e.R) = (e.R) (<F8_Add (e.X) <F8_Mul (e.Y) e.Q >>);
         }