## GF(2**n) support in ARIBAS

As of version 1.50, ARIBAS offers direct support for the fields GF(2**n) of characteristic 2.
To be able to calculate in GF(2**n), the field must first be initialized by the command `gf2n_init(n)`, where n is the degree of the field over GF(2). Example:
```    ==> gf2n_init(53).
9_00719_92547_41063
```
This function calculates an irreducible polynomial f(X) of degree n (here n = 53). (The return value is an encoding of this polynomial.) The field GF(2**n) is then represented as GF(2)[X]/(f(X)), its elements as polynomials mod f(X), which have a uniquely defined representative of degree < n. Such a polynomial
```    g(X) = sum(a_i * X**i: 0 <= i < n),    a_i = 0,1,
```
can be regarded as a bitvector of length n. In ARIBAS the data type of elements in GF(2**n) is called `gf2nint`, the literals of this data type have the prefix `2x` followed by the hexadecimal representation of the bitvector. Also base 2 and base 8 representation is allowed; in this case the prefix is `2y` resp. `2o`. The zero and unit elements of GF(2**n) are `2x0` and `2x1`. A random element of GF(2**n) can be generated by
```    ==> x := gf2nint(random(2**53)).
-: 2x7_FF23_0C47_07BE
```
(The function
```    gf2nint(n: integer): gf2nint;
```
transforms integers to data type `gf2nint`.)
Let's generate a second random element of GF(2**53)
```    ==> y := gf2nint(random(2**53)).
-: 2x13_C4A3_92A9_D731
```
We can add, multiply and divide these elements:
```    ==> x + y.
-: 2x14_3B80_9EEE_D08F

==> x*y.
-: 2x15_069C_F71C_C1BD

==> z1 := x+y.
-: 2x14_3B80_9EEE_D08F

==> z2 := x*y.
-: 2x15_069C_F71C_C1BD

==> z3 := x/y.
-: 2x15_F736_CC28_0101

==> z1 + y.
-: 2x7_FF23_0C47_07BE

==> z3 * y.
-: 2x7_FF23_0C47_07BE
```
(Note that `(x + y) + y = x`, since in GF(2**n) addition is the same as subtraction.)
Another operation is exponentiation of an `gf2nint` by an integer, where the exponent may also be negative.
```    ==> x**-1.
-: 2x13_CF16_5F28_DCA4

==> _ * x.
-: 2x1

==> x**(2**53 - 1).
-: 2x1
```
The last result comes from the fact that the multiplicative group of GF(2**n) has order 2**n - 1. Another example for exponentiation: Every element x of GF(2**n) is a square. Its square root can be calculated by raising x to the power 2**(n-1). Example:
```    ==> u := x**(2**52).
-: 2x4_615D_D2E9_7C49

==> u**2.
-: 2x7_FF23_0C47_07BE

==> _ = x.
-: true
```
Other functions:
```    gf2n_degree(): integer;
```
There is always only one field GF(2**n) active. This function returns its degree.
```    gf2n_fieldpol(): integer;
```
Returns the irreducible polynomial serving to define the active field GF(2**n). This polynomial is encoded as an integer; an integer f in binary representation
```    f = sum(a_i * 2**i: 0 <= i <= n), a_i = 0,1
```
represents the polynomial
```    f(X) = sum(a_i * X**i: 0 <= i <= n).
```
Example: If GF(2**53) is active, then
```==> f := gf2n_fieldpol().
-: 9_00719_92547_41063

==> write(f:base(2)).
100000_00000000_00000000_00000000_00000000_00000000_01000111
-: 1
```
This means that
```    f(X) = X**53 + X**6 + X**2 + X + 1.
```
The trace Tr: GF(2**n) --> {0,1} can be calculated by the function
```    gf2n_trace(x: gf2nint): integer;
```
Elliptic Curves: Examples of using the functions and operations in GF(2**n) for elliptic curves over GF(2**n) can be studied in the file `ec_gf2n.ari`.

Homepage of ARIBAS

Otto Forster 2004-08-16