$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 >>); }