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