CECCO: Finite Extension Fields

CECCO supports finite extension fields, their arithmetic, and their properties. The irreducible polynomials required for constructing finite extension fields can be obtained as described here. The focus in this demo is on field construction and inter-field relationships, working with finite extension fields (arithmetic, properties) is identical to working with prime fields as described here.

The main example here is based on the binary field F2, but CECCO can deal with finite fields of any characteristic.

code.cpp Lines 7–14

    using F2 = Fp<2>;
    using F8 = Ext<F2, {1, 0, 1, 1}>;
    std::cout << "Show textual info about F8:" << std::endl;
    std::cout << F8::get_info() << std::endl << std::endl;

    using F64_a = Ext<F8, {6, 2, 1}>;
    std::cout << "Show textual info about F64_a:" << std::endl;
    std::cout << F64_a::get_info() << std::endl << std::endl;

Show textual info about F8:
finite field with 8 elements, specified as degree 3 extension of (prime field with 2 elements), irreducible polynomial 1 + x^2 + x^3

Show textual info about F64_a:
finite field with 64 elements, specified as degree 2 extension of (finite field with 8 elements, specified as degree 3 extension of (prime field with 2 elements), irreducible polynomial 1 + x^2 + x^3), irreducible polynomial 6 + 2x + x^2

Field operations are based on precomputed lookup tables (LUTs). These LUTs can be displayed for debugging purposes:

code.cpp Lines 16–16

    F8::show_tables();

addition table (row and column headers omitted)
0, 1, 2, 3, 4, 5, 6, 7, 
1, 0, 3, 2, 5, 4, 7, 6, 
2, 3, 0, 1, 6, 7, 4, 5, 
3, 2, 1, 0, 7, 6, 5, 4, 
4, 5, 6, 7, 0, 1, 2, 3, 
5, 4, 7, 6, 1, 0, 3, 2, 
6, 7, 4, 5, 2, 3, 0, 1, 
7, 6, 5, 4, 3, 2, 1, 0, 
additive inverse table (row and column headers omitted)
0
1
2
3
4
5
6
7
multiplication table (row and column headers omitted)
0, 0, 0, 0, 0, 0, 0, 0, 
0, 1, 2, 3, 4, 5, 6, 7, 
0, 2, 4, 6, 5, 7, 1, 3, 
0, 3, 6, 5, 1, 2, 7, 4, 
0, 4, 5, 1, 7, 3, 2, 6, 
0, 5, 7, 2, 3, 6, 4, 1, 
0, 6, 1, 7, 2, 4, 3, 5, 
0, 7, 3, 4, 6, 1, 5, 2, 
multiplicative inverse table (row and column headers omitted)
0
1
6
4
3
7
2
5
multiplicative order table (row and column headers omitted)
0
1
7
7
7
7
7
7
element coefficients table (row and column headers omitted)
0: 0, 0, 0, 
1: 0, 0, 1, 
2: 0, 1, 0, 
3: 0, 1, 1, 
4: 1, 0, 0, 
5: 1, 0, 1, 
6: 1, 1, 0, 
7: 1, 1, 1, 
generator (with mult. order)
3 (7)

By default, LUTs are calculated at runtime, and Ext<F2, {1, 1, 1}> is identical to Ext<F2, {1, 1, 1}, LutMode::RunTime>. Optionally, LUTs can be calculated at compile time and embedded in the executable:

code.cpp Lines 19–19

    using F4 = Ext<F2, {1, 1, 1}, LutMode::CompileTime>;

Compile-time LUT calculation leads to slightly improved runtime performance and results in zero program startup time. Downside: Compile-time calculation can exceed the recursion limits of the compiler consume large amounts of memory. Compiler limits can be tweaked with -fconstexpr-depth=4294967295 -fconstexpr-steps=4294967295 (clang++) or -fconstexpr-ops-limit=4294967295 (g++). Recommendation: Use compile-time LUTs for small fields (up to about 150 elements).

Compile-time LUT calculation is only possible if the base field also uses compile-time LUTs!

code.cpp Lines 21–23

    using F64_b = Ext<F4, {3, 1, 2, 1}, LutMode::CompileTime>;
    std::cout << "Show textual info about F64_b:" << std::endl;
    std::cout << F64_b::get_info() << std::endl;

Show textual info about F64_b:
finite field with 64 elements, specified as degree 3 extension of (finite field with 4 elements, specified as degree 2 extension of (prime field with 2 elements), irreducible polynomial 1 + x + x^2), irreducible polynomial 3 + x + 2x^2 + x^3

F64_a and F64_b are isomorphic, so we can transition between the two:

code.cpp Lines 25–29

    auto phi = Isomorphism<F64_a, F64_b>();
    auto a = F64_a().randomize();  // random element of F64_a, type: F64_a
    std::cout << "Random element in F64_a: " << a << std::endl;
    auto b = phi(a);  // representation of a in F64_b, type: F64_b
    std::cout << "Same element in F64_b: " << b << std::endl;

The following two lines are equivalent: Isomorphism<F64_b, F64_a> is automatically instantiated as the inverse of Isomorphism<F64_a, F64_b>.

code.cpp Lines 31–36

    auto c = phi.inverse()(b);  // type: F64_a
    // auto c = Isomorphism<F64_b, F64_a>()(b);

    std::cout << "... back in F64_a: " << c << std::endl;
    assert(a == c);
    std::cout << std::endl;

Random element in F64_a: 36
Same element in F64_b: 24
... back in F64_a: 36

Yet another isomorphic field with 64 elements:

code.cpp Lines 38–40

    using F64_c = Ext<F2, {1, 0, 0, 1, 0, 0, 1}>;
    std::cout << "Show textual info about F64_c:" << std::endl;
    std::cout << F64_c::get_info() << std::endl << std::endl;

Show textual info about F64_c:
finite field with 64 elements, specified as degree 6 extension of (prime field with 2 elements), irreducible polynomial 1 + x^3 + x^6

At this point: Three "field towers" (all with characteristic 2): F2 -> F8 -> F64_a, F2 -> F4 -> F64_b, F2 -> F64_c. Together, these form a tree with F2 at the root. We can merge vertices of isomorphic fields to obtain a true finite field lattice with intersections:

code.cpp Lines 42–67

    using F64 = Iso<F64_c, F64_b, F64_a>;
    std::cout << "Show textual info about F64:" << std::endl;
    std::cout << F64::get_info() << std::endl;

    static_assert(SubfieldOf<F64, F2>);
    static_assert(SubfieldOf<F64, F4>);
    static_assert(SubfieldOf<F64, F8>);
    static_assert(SubfieldOf<F64, F64_a>);
    static_assert(SubfieldOf<F64, F64_b>);
    static_assert(SubfieldOf<F64, F64_c>);
    static_assert(SubfieldOf<F64, F64>);
    // other superfield relations
    static_assert(SubfieldOf<F64_a, F64_a>);
    static_assert(SubfieldOf<F64_a, F2>);
    static_assert(SubfieldOf<F64_a, F8>);
    static_assert(SubfieldOf<F64_b, F64_b>);
    static_assert(SubfieldOf<F64_b, F2>);
    static_assert(SubfieldOf<F64_b, F4>);
    static_assert(SubfieldOf<F8, F8>);
    static_assert(SubfieldOf<F8, F2>);
    static_assert(SubfieldOf<F4, F4>);
    static_assert(SubfieldOf<F4, F2>);
    // superfield non-relations
    static_assert(!SubfieldOf<F8, F4>);
    static_assert(!SubfieldOf<F64_a, F4>);
    static_assert(!SubfieldOf<F64_b, F8>);

Show textual info about F64:
stack of isomorphic fields, main field: finite field with 64 elements, specified as degree 6 extension of (prime field with 2 elements), irreducible polynomial 1 + x^3 + x^6

Sub-/Superfield casts: Every subfield element can be safely up-cast to a superfield element. In this mapping, 0 is always mapped to 0 and 1 to 1 of the superfield:

code.cpp Lines 69–76

    auto d = F2().randomize();
    std::cout << "d: " << d << std::endl;
    F8 e(d);
    std::cout << "e: " << e << std::endl;
    F64 f(e);
    std::cout << "f: " << f << std::endl;
    F64 g(d);
    std::cout << "g: " << g << std::endl;

d: 1
e: 1
f: 1
g: 1

This is more interesting if the subfield has more elements:

code.cpp Lines 78–81

    auto h = F8().randomize();
    std::cout << "h: " << h << std::endl;
    F64 i(h);
    std::cout << "i: " << i << std::endl;

h: 6
i: 48

In general: h will "look" different from i, but still the following always succeeds: F8(i) is a "down-cast" from F64 to its subfield F8:

code.cpp Lines 84–84

    assert(h == F8(i));

Downcasts can fail. First, check the labels of all elements of F8 after they are up-cast to F64::

code.cpp Lines 87–89

    std::cout << "Elements of F8 after casting them to superfield F64: " << std::endl;
    for (size_t i = 0; i < F8::get_q(); ++i) std::cout << F64(F8(i)) << " ";
    std::cout << std::endl;

Elements of F8 after casting them to superfield F64: 
0 1 39 38 23 22 48 49

Downcasting any of them to F8 works as expected:

code.cpp Lines 91–91

    std::cout << "6 in F64 coincides with " << F8(F64(F8(3))) << " in F8" << std::endl;

6 in F64 coincides with 3 in F8

However, downcasting an element j from F64 that is not an embedded element of F8 will throw an exception:

code.cpp Lines 93–99

    F64 j(43);
    std::cout << "j: " << j << std::endl;
    try {
        std::cout << F8(j) << std::endl;
    } catch (std::invalid_argument& e) {
        std::cout << "down-casting " << j << " from F64 to F8 is not possible: " << e.what() << std::endl;
    }

j: 43
down-casting 43 from F64 to F8 is not possible: superfield element is not in subfield

We can construct anything that is mathematically possible, but anything that has not been constructed does not exist in our program. For example, we could have constructed F16 in two different ways, but in this demo we did not. Thus, F16 cannot be used in this demo. We can do wild cross-casts (automatically through the largest common subfield) within our constructed lattice:

code.cpp Lines 101–115

    auto k = F2().randomize();
    F4 l(k);
    F64 m(l);
    F8 n(m);
    F2 o(n);
    assert(k == o);

    auto p = F4().randomize();
    F64 q(p);
    try {
        F8 r(q);
        std::cout << "Up-casting " << p << " from F4 to F64 and then down-casting it to F8 gives " << r << std::endl;
    } catch (std::invalid_argument& e) {
        std::cout << "down-casting " << q << " from F64 to F8 is not possible: " << e.what() << std::endl;
    }

Up-casting 1 from F4 to F64 and then down-casting it to F8 gives 1

Any Ext or Iso element can be expanded into a vector over any constructed subfield:

code.cpp Lines 117–120

    std::cout << "j from F64 (see above) as vector over F2: " << j.as_vector<F2>() << std::endl;
    std::cout << "j from F64 (see above) as vector over F4: " << j.as_vector<F4>() << std::endl;
    std::cout << "j from F64 (see above) as vector over F8: " << j.as_vector<F8>() << std::endl;

j from F64 (see above) as vector over F2: ( 1, 0, 1, 0, 1, 1 )
j from F64 (see above) as vector over F4: ( 0, 3, 2 )
j from F64 (see above) as vector over F8: ( 1, 5 )

The original superfield element can always be recovered from such vectors:

code.cpp Lines 121–123

    assert(j == F64(j.as_vector<F2>()));
    assert(j == F64(j.as_vector<F4>()));
    assert(j == F64(j.as_vector<F8>()));

Expansion into subfield vectors is compatible with addition:

code.cpp Lines 125–127

    assert(i + j == F64(i.as_vector<F2>() + j.as_vector<F2>()));
    assert(i + j == F64(i.as_vector<F4>() + j.as_vector<F4>()));
    assert(i + j == F64(i.as_vector<F8>() + j.as_vector<F8>()));

Isomorphisms between fields of the same size are compatible with addition and multiplication:

code.cpp Lines 129–194

    {
        auto x = F64_a().randomize();
        auto y = F64_a().randomize();
        assert((Isomorphism<F64_a, F64_a>()(x + y)) ==
               (Isomorphism<F64_a, F64_a>()(x) + Isomorphism<F64_a, F64_a>()(y)));
        assert((Isomorphism<F64_a, F64_a>()(x * y)) ==
               (Isomorphism<F64_a, F64_a>()(x) * Isomorphism<F64_a, F64_a>()(y)));
        assert((Isomorphism<F64_a, F64_b>()(x + y)) ==
               (Isomorphism<F64_a, F64_b>()(x) + Isomorphism<F64_a, F64_b>()(y)));
        assert((Isomorphism<F64_a, F64_b>()(x * y)) ==
               (Isomorphism<F64_a, F64_b>()(x) * Isomorphism<F64_a, F64_b>()(y)));
        assert((Isomorphism<F64_a, F64_c>()(x + y)) ==
               (Isomorphism<F64_a, F64_c>()(x) + Isomorphism<F64_a, F64_c>()(y)));
        assert((Isomorphism<F64_a, F64_c>()(x * y)) ==
               (Isomorphism<F64_a, F64_c>()(x) * Isomorphism<F64_a, F64_c>()(y)));
        assert((Isomorphism<F64_a, F64>()(x + y)) == (Isomorphism<F64_a, F64>()(x) + Isomorphism<F64_a, F64>()(y)));
        assert((Isomorphism<F64_a, F64>()(x * y)) == (Isomorphism<F64_a, F64>()(x) * Isomorphism<F64_a, F64>()(y)));
    }
    {
        auto x = F64_b().randomize();
        auto y = F64_b().randomize();
        assert((Isomorphism<F64_b, F64_a>()(x + y)) ==
               (Isomorphism<F64_b, F64_a>()(x) + Isomorphism<F64_b, F64_a>()(y)));
        assert((Isomorphism<F64_b, F64_a>()(x * y)) ==
               (Isomorphism<F64_b, F64_a>()(x) * Isomorphism<F64_b, F64_a>()(y)));
        assert((Isomorphism<F64_b, F64_b>()(x + y)) ==
               (Isomorphism<F64_b, F64_b>()(x) + Isomorphism<F64_b, F64_b>()(y)));
        assert((Isomorphism<F64_b, F64_b>()(x * y)) ==
               (Isomorphism<F64_b, F64_b>()(x) * Isomorphism<F64_b, F64_b>()(y)));
        assert((Isomorphism<F64_b, F64_c>()(x + y)) ==
               (Isomorphism<F64_b, F64_c>()(x) + Isomorphism<F64_b, F64_c>()(y)));
        assert((Isomorphism<F64_b, F64_c>()(x * y)) ==
               (Isomorphism<F64_b, F64_c>()(x) * Isomorphism<F64_b, F64_c>()(y)));
        assert((Isomorphism<F64_b, F64>()(x + y)) == (Isomorphism<F64_b, F64>()(x) + Isomorphism<F64_b, F64>()(y)));
        assert((Isomorphism<F64_b, F64>()(x * y)) == (Isomorphism<F64_b, F64>()(x) * Isomorphism<F64_b, F64>()(y)));
    }
    {
        auto x = F64_c().randomize();
        auto y = F64_c().randomize();
        assert((Isomorphism<F64_c, F64_a>()(x + y)) ==
               (Isomorphism<F64_c, F64_a>()(x) + Isomorphism<F64_c, F64_a>()(y)));
        assert((Isomorphism<F64_c, F64_a>()(x * y)) ==
               (Isomorphism<F64_c, F64_a>()(x) * Isomorphism<F64_c, F64_a>()(y)));
        assert((Isomorphism<F64_c, F64_b>()(x + y)) ==
               (Isomorphism<F64_c, F64_b>()(x) + Isomorphism<F64_c, F64_b>()(y)));
        assert((Isomorphism<F64_c, F64_b>()(x * y)) ==
               (Isomorphism<F64_c, F64_b>()(x) * Isomorphism<F64_c, F64_b>()(y)));
        assert((Isomorphism<F64_c, F64_c>()(x + y)) ==
               (Isomorphism<F64_c, F64_c>()(x) + Isomorphism<F64_c, F64_c>()(y)));
        assert((Isomorphism<F64_c, F64_c>()(x * y)) ==
               (Isomorphism<F64_c, F64_c>()(x) * Isomorphism<F64_c, F64_c>()(y)));
        assert((Isomorphism<F64_c, F64>()(x + y)) == (Isomorphism<F64_c, F64>()(x) + Isomorphism<F64_c, F64>()(y)));
        assert((Isomorphism<F64_c, F64>()(x * y)) == (Isomorphism<F64_c, F64>()(x) * Isomorphism<F64_c, F64>()(y)));
    }
    {
        auto x = F64().randomize();
        auto y = F64().randomize();
        assert((Isomorphism<F64, F64_a>()(x + y)) == (Isomorphism<F64, F64_a>()(x) + Isomorphism<F64, F64_a>()(y)));
        assert((Isomorphism<F64, F64_a>()(x * y)) == (Isomorphism<F64, F64_a>()(x) * Isomorphism<F64, F64_a>()(y)));
        assert((Isomorphism<F64, F64_b>()(x + y)) == (Isomorphism<F64, F64_b>()(x) + Isomorphism<F64, F64_b>()(y)));
        assert((Isomorphism<F64, F64_b>()(x * y)) == (Isomorphism<F64, F64_b>()(x) * Isomorphism<F64, F64_b>()(y)));
        assert((Isomorphism<F64, F64_c>()(x + y)) == (Isomorphism<F64, F64_c>()(x) + Isomorphism<F64, F64_c>()(y)));
        assert((Isomorphism<F64, F64_c>()(x * y)) == (Isomorphism<F64, F64_c>()(x) * Isomorphism<F64, F64_c>()(y)));
        assert((Isomorphism<F64, F64>()(x + y)) == (Isomorphism<F64, F64>()(x) + Isomorphism<F64, F64>()(y)));
        assert((Isomorphism<F64, F64>()(x * y)) == (Isomorphism<F64, F64>()(x) * Isomorphism<F64, F64>()(y)));
    }

CECCO is not restricted to characteristic 2:

code.cpp Lines 196–218

    using F3 = Fp<3>;
    using F9 = Ext<F3, {2, 2, 1}, LutMode::CompileTime>;
    using F27 = Ext<F3, {1, 2, 0, 1}, LutMode::CompileTime>;
    using F81_a = Ext<F3, {2, 1, 0, 0, 1}>;
    using F81_b = Ext<F9, {6, 0, 1}>;
    using F81 = Iso<F81_a, F81_b>;
    using F243 = Ext<F3, {2, 0, 1, 2, 1, 1}>;
    using F729_a = Ext<F3, {2, 1, 2, 0, 1, 0, 1}>;
    using F729_b = Ext<F9, {7, 0, 6, 1}>;
    using F729_c = Ext<F27, {14, 20, 1}>;
    using F729 = Iso<F729_a, F729_b, F729_c>;

    auto s = F9().randomize();
    std::cout << "s: " << s << std::endl;
    F729 t(s);
    std::cout << "t: " << t << std::endl;
    std::cout << "Checking if s == F9(t): s=" << s << ", t=" << t << std::endl;
    assert(s == F9(t));

    auto u = F729().randomize();
    std::cout << u << " (from F729) as vector with components from subfield F27: " << u.as_vector<F27>() << std::endl;
    auto v = F729().randomize();
    assert(u + v == F729(u.as_vector<F27>() + v.as_vector<F27>()));

s: 2
t: 2
Checking if s == F9(t): s=2, t=2
220 (from F729) as vector with components from subfield F27: ( 3, 0 )

A complete, compilable demo is shown below:

code.cpp

#include <iostream>

#include "cecco.hpp"
using namespace CECCO;

int main(void) {
    using F2 = Fp<2>;
    using F8 = Ext<F2, {1, 0, 1, 1}>;
    std::cout << "Show textual info about F8:" << std::endl;
    std::cout << F8::get_info() << std::endl << std::endl;

    using F64_a = Ext<F8, {6, 2, 1}>;
    std::cout << "Show textual info about F64_a:" << std::endl;
    std::cout << F64_a::get_info() << std::endl << std::endl;

    F8::show_tables();
    std::cout << std::endl;

    using F4 = Ext<F2, {1, 1, 1}, LutMode::CompileTime>;

    using F64_b = Ext<F4, {3, 1, 2, 1}, LutMode::CompileTime>;
    std::cout << "Show textual info about F64_b:" << std::endl;
    std::cout << F64_b::get_info() << std::endl;

    auto phi = Isomorphism<F64_a, F64_b>();
    auto a = F64_a().randomize();  // random element of F64_a, type: F64_a
    std::cout << "Random element in F64_a: " << a << std::endl;
    auto b = phi(a);  // representation of a in F64_b, type: F64_b
    std::cout << "Same element in F64_b: " << b << std::endl;

    auto c = phi.inverse()(b);  // type: F64_a
    // auto c = Isomorphism<F64_b, F64_a>()(b);

    std::cout << "... back in F64_a: " << c << std::endl;
    assert(a == c);
    std::cout << std::endl;

    using F64_c = Ext<F2, {1, 0, 0, 1, 0, 0, 1}>;
    std::cout << "Show textual info about F64_c:" << std::endl;
    std::cout << F64_c::get_info() << std::endl << std::endl;

    using F64 = Iso<F64_c, F64_b, F64_a>;
    std::cout << "Show textual info about F64:" << std::endl;
    std::cout << F64::get_info() << std::endl;

    static_assert(SubfieldOf<F64, F2>);
    static_assert(SubfieldOf<F64, F4>);
    static_assert(SubfieldOf<F64, F8>);
    static_assert(SubfieldOf<F64, F64_a>);
    static_assert(SubfieldOf<F64, F64_b>);
    static_assert(SubfieldOf<F64, F64_c>);
    static_assert(SubfieldOf<F64, F64>);
    // other superfield relations
    static_assert(SubfieldOf<F64_a, F64_a>);
    static_assert(SubfieldOf<F64_a, F2>);
    static_assert(SubfieldOf<F64_a, F8>);
    static_assert(SubfieldOf<F64_b, F64_b>);
    static_assert(SubfieldOf<F64_b, F2>);
    static_assert(SubfieldOf<F64_b, F4>);
    static_assert(SubfieldOf<F8, F8>);
    static_assert(SubfieldOf<F8, F2>);
    static_assert(SubfieldOf<F4, F4>);
    static_assert(SubfieldOf<F4, F2>);
    // superfield non-relations
    static_assert(!SubfieldOf<F8, F4>);
    static_assert(!SubfieldOf<F64_a, F4>);
    static_assert(!SubfieldOf<F64_b, F8>);

    auto d = F2().randomize();
    std::cout << "d: " << d << std::endl;
    F8 e(d);
    std::cout << "e: " << e << std::endl;
    F64 f(e);
    std::cout << "f: " << f << std::endl;
    F64 g(d);
    std::cout << "g: " << g << std::endl;

    auto h = F8().randomize();
    std::cout << "h: " << h << std::endl;
    F64 i(h);
    std::cout << "i: " << i << std::endl;
    std::cout << "Checking if h == F8(i): h=" << h << ", i=" << i << std::endl;
    // F8(i) is a "down-cast" from F64 to its subfield F8
    assert(h == F8(i));

    // Downcasts can fail! First, check the labels of all elements of F8 when up-cast to F64:
    std::cout << "Elements of F8 after casting them to superfield F64: " << std::endl;
    for (size_t i = 0; i < F8::get_q(); ++i) std::cout << F64(F8(i)) << " ";
    std::cout << std::endl;
    // Downcasting any of them to F8 certainly works:
    std::cout << "6 in F64 coincides with " << F8(F64(F8(3))) << " in F8" << std::endl;
    // However, downcasting some j from F64 that is not an embedded element of F8 will throw
    F64 j(43);
    std::cout << "j: " << j << std::endl;
    try {
        std::cout << F8(j) << std::endl;
    } catch (std::invalid_argument& e) {
        std::cout << "down-casting " << j << " from F64 to F8 is not possible: " << e.what() << std::endl;
    }

    auto k = F2().randomize();
    F4 l(k);
    F64 m(l);
    F8 n(m);
    F2 o(n);
    assert(k == o);

    auto p = F4().randomize();
    F64 q(p);
    try {
        F8 r(q);
        std::cout << "Up-casting " << p << " from F4 to F64 and then down-casting it to F8 gives " << r << std::endl;
    } catch (std::invalid_argument& e) {
        std::cout << "down-casting " << q << " from F64 to F8 is not possible: " << e.what() << std::endl;
    }

    std::cout << "j from F64 (see above) as vector over F2: " << j.as_vector<F2>() << std::endl;
    std::cout << "j from F64 (see above) as vector over F4: " << j.as_vector<F4>() << std::endl;
    std::cout << "j from F64 (see above) as vector over F8: " << j.as_vector<F8>() << std::endl;

    assert(j == F64(j.as_vector<F2>()));
    assert(j == F64(j.as_vector<F4>()));
    assert(j == F64(j.as_vector<F8>()));

    assert(i + j == F64(i.as_vector<F2>() + j.as_vector<F2>()));
    assert(i + j == F64(i.as_vector<F4>() + j.as_vector<F4>()));
    assert(i + j == F64(i.as_vector<F8>() + j.as_vector<F8>()));

    {
        auto x = F64_a().randomize();
        auto y = F64_a().randomize();
        assert((Isomorphism<F64_a, F64_a>()(x + y)) ==
               (Isomorphism<F64_a, F64_a>()(x) + Isomorphism<F64_a, F64_a>()(y)));
        assert((Isomorphism<F64_a, F64_a>()(x * y)) ==
               (Isomorphism<F64_a, F64_a>()(x) * Isomorphism<F64_a, F64_a>()(y)));
        assert((Isomorphism<F64_a, F64_b>()(x + y)) ==
               (Isomorphism<F64_a, F64_b>()(x) + Isomorphism<F64_a, F64_b>()(y)));
        assert((Isomorphism<F64_a, F64_b>()(x * y)) ==
               (Isomorphism<F64_a, F64_b>()(x) * Isomorphism<F64_a, F64_b>()(y)));
        assert((Isomorphism<F64_a, F64_c>()(x + y)) ==
               (Isomorphism<F64_a, F64_c>()(x) + Isomorphism<F64_a, F64_c>()(y)));
        assert((Isomorphism<F64_a, F64_c>()(x * y)) ==
               (Isomorphism<F64_a, F64_c>()(x) * Isomorphism<F64_a, F64_c>()(y)));
        assert((Isomorphism<F64_a, F64>()(x + y)) == (Isomorphism<F64_a, F64>()(x) + Isomorphism<F64_a, F64>()(y)));
        assert((Isomorphism<F64_a, F64>()(x * y)) == (Isomorphism<F64_a, F64>()(x) * Isomorphism<F64_a, F64>()(y)));
    }
    {
        auto x = F64_b().randomize();
        auto y = F64_b().randomize();
        assert((Isomorphism<F64_b, F64_a>()(x + y)) ==
               (Isomorphism<F64_b, F64_a>()(x) + Isomorphism<F64_b, F64_a>()(y)));
        assert((Isomorphism<F64_b, F64_a>()(x * y)) ==
               (Isomorphism<F64_b, F64_a>()(x) * Isomorphism<F64_b, F64_a>()(y)));
        assert((Isomorphism<F64_b, F64_b>()(x + y)) ==
               (Isomorphism<F64_b, F64_b>()(x) + Isomorphism<F64_b, F64_b>()(y)));
        assert((Isomorphism<F64_b, F64_b>()(x * y)) ==
               (Isomorphism<F64_b, F64_b>()(x) * Isomorphism<F64_b, F64_b>()(y)));
        assert((Isomorphism<F64_b, F64_c>()(x + y)) ==
               (Isomorphism<F64_b, F64_c>()(x) + Isomorphism<F64_b, F64_c>()(y)));
        assert((Isomorphism<F64_b, F64_c>()(x * y)) ==
               (Isomorphism<F64_b, F64_c>()(x) * Isomorphism<F64_b, F64_c>()(y)));
        assert((Isomorphism<F64_b, F64>()(x + y)) == (Isomorphism<F64_b, F64>()(x) + Isomorphism<F64_b, F64>()(y)));
        assert((Isomorphism<F64_b, F64>()(x * y)) == (Isomorphism<F64_b, F64>()(x) * Isomorphism<F64_b, F64>()(y)));
    }
    {
        auto x = F64_c().randomize();
        auto y = F64_c().randomize();
        assert((Isomorphism<F64_c, F64_a>()(x + y)) ==
               (Isomorphism<F64_c, F64_a>()(x) + Isomorphism<F64_c, F64_a>()(y)));
        assert((Isomorphism<F64_c, F64_a>()(x * y)) ==
               (Isomorphism<F64_c, F64_a>()(x) * Isomorphism<F64_c, F64_a>()(y)));
        assert((Isomorphism<F64_c, F64_b>()(x + y)) ==
               (Isomorphism<F64_c, F64_b>()(x) + Isomorphism<F64_c, F64_b>()(y)));
        assert((Isomorphism<F64_c, F64_b>()(x * y)) ==
               (Isomorphism<F64_c, F64_b>()(x) * Isomorphism<F64_c, F64_b>()(y)));
        assert((Isomorphism<F64_c, F64_c>()(x + y)) ==
               (Isomorphism<F64_c, F64_c>()(x) + Isomorphism<F64_c, F64_c>()(y)));
        assert((Isomorphism<F64_c, F64_c>()(x * y)) ==
               (Isomorphism<F64_c, F64_c>()(x) * Isomorphism<F64_c, F64_c>()(y)));
        assert((Isomorphism<F64_c, F64>()(x + y)) == (Isomorphism<F64_c, F64>()(x) + Isomorphism<F64_c, F64>()(y)));
        assert((Isomorphism<F64_c, F64>()(x * y)) == (Isomorphism<F64_c, F64>()(x) * Isomorphism<F64_c, F64>()(y)));
    }
    {
        auto x = F64().randomize();
        auto y = F64().randomize();
        assert((Isomorphism<F64, F64_a>()(x + y)) == (Isomorphism<F64, F64_a>()(x) + Isomorphism<F64, F64_a>()(y)));
        assert((Isomorphism<F64, F64_a>()(x * y)) == (Isomorphism<F64, F64_a>()(x) * Isomorphism<F64, F64_a>()(y)));
        assert((Isomorphism<F64, F64_b>()(x + y)) == (Isomorphism<F64, F64_b>()(x) + Isomorphism<F64, F64_b>()(y)));
        assert((Isomorphism<F64, F64_b>()(x * y)) == (Isomorphism<F64, F64_b>()(x) * Isomorphism<F64, F64_b>()(y)));
        assert((Isomorphism<F64, F64_c>()(x + y)) == (Isomorphism<F64, F64_c>()(x) + Isomorphism<F64, F64_c>()(y)));
        assert((Isomorphism<F64, F64_c>()(x * y)) == (Isomorphism<F64, F64_c>()(x) * Isomorphism<F64, F64_c>()(y)));
        assert((Isomorphism<F64, F64>()(x + y)) == (Isomorphism<F64, F64>()(x) + Isomorphism<F64, F64>()(y)));
        assert((Isomorphism<F64, F64>()(x * y)) == (Isomorphism<F64, F64>()(x) * Isomorphism<F64, F64>()(y)));
    }

    using F3 = Fp<3>;
    using F9 = Ext<F3, {2, 2, 1}, LutMode::CompileTime>;
    using F27 = Ext<F3, {1, 2, 0, 1}, LutMode::CompileTime>;
    using F81_a = Ext<F3, {2, 1, 0, 0, 1}>;
    using F81_b = Ext<F9, {6, 0, 1}>;
    using F81 = Iso<F81_a, F81_b>;
    using F243 = Ext<F3, {2, 0, 1, 2, 1, 1}>;
    using F729_a = Ext<F3, {2, 1, 2, 0, 1, 0, 1}>;
    using F729_b = Ext<F9, {7, 0, 6, 1}>;
    using F729_c = Ext<F27, {14, 20, 1}>;
    using F729 = Iso<F729_a, F729_b, F729_c>;

    auto s = F9().randomize();
    std::cout << "s: " << s << std::endl;
    F729 t(s);
    std::cout << "t: " << t << std::endl;
    std::cout << "Checking if s == F9(t): s=" << s << ", t=" << t << std::endl;
    assert(s == F9(t));

    auto u = F729().randomize();
    std::cout << u << " (from F729) as vector with components from subfield F27: " << u.as_vector<F27>() << std::endl;
    auto v = F729().randomize();
    assert(u + v == F729(u.as_vector<F27>() + v.as_vector<F27>()));

    return 0;
}