Fields in SymEngine

Fields module implements the GaloisField concept in SymEngine. The GaloisField class has been derived from UIntPolyBase as:

class GaloisField : public UIntPolyBase<GaloisFieldDict, GaloisField>

This allows us to use, add_poly, mul_poly and other Univariate Polynomial functions.

About Univariate Polynomial

GaloisField as it is derived from UIntPolyBase, we have the private variable poly_ which is of type GaloisFieldDict and var_ which stores the variable name of polynomial. So, with a GaloisField object we can represent a polynomial in different fields, like:

GaloisField::from_vec(x, {17_z, 0_z, 7_z, 9_z, 7_z, 14_z}, 7_z);

represents 14*x**5 + 7*x**4 + 9*x**3 + 7*x**2 + 17 in GF(7) i.e. 2*x**3 + 3. And all the operations which can be done on Univariate Integer Polynomial can be done on it, like:

    RCP<const Symbol> x = symbol("x");
    a = {1_z, 2_z, 3_z};
    r1 = GaloisField::from_vec(x, a, 11_z); // 3*x**2 + 2*x + 1
    r2 = neg_upoly(*r1); // negates the polynomial in the field
    REQUIRE(r2->__str__() == "8*x**2 + 9*x + 10");
    r2 = add_upoly(*r1, *GaloisField::from_vec(x, {4_z, 13_z}, 11_z)); // adds `2*x + 4` to `r1`
    REQUIRE(r2->__str__() == "3*x**2 + 4*x + 5");
    r2 = sub_upoly(*r1, *GaloisField::from_vec(x, {1_z, 13_z}, 11_z)); // subtracts `13*x + 1` from `r1`
    REQUIRE(r2->__str__() == "3*x**2");

And apart from it, The various operations of a finite field are implemented in GaloisFieldDict class. The GaloisFieldDict is a dense representation, having a vector of integer_class with size equal to polynomial's degree + 1 named dict_ and an integer_class object for storing the characteristics of the field name modulo_.

Example a polynomial:

x**5 + 9x + 2

in GF(5) will have the representation as:

dict_ = [2, 4, 0, 0, 0, 1]
modulo_ = 5

so dict_[i] is the coefficient of i`th degree of variable in the polynomial.

All the operations ensure that there is no leading zero in the representation i.e. all the polynomials are stripped using gf_istrip. That means, we can't have: [2, 4, 0, 0, 0, 1, 0, 0] represent x**5 + 9x + 2

This enables us to get the degree by

unsigned degree() const
{
    if (dict_.empty())
        return 0;
    return dict_.size() - 1;
}

The arithmetic operators +, -, *, /, % are overloaded for the GaloisFieldDict class as:

template <typename T>
friend GaloisFieldDict operator+(const GaloisFieldDict &a, const T &b); //Currently  T can be `GaloisFieldDict` or `integer_class`.
// Similarly for '-', '*', '/', '%'

GaloisFieldDict operator-() const; // This negates the `dict_`

GaloisFieldDict &operator+=(const GaloisFieldDict &other);
GaloisFieldDict &operator+=(const integer_class &other);
// Similarly for '-', '*', '/', '%'

// And for powering, we have:
static GaloisFieldDict pow(const GaloisFieldDict &a, unsigned int p);
GaloisFieldDict gf_pow(const unsigned int n) const; // `a.gf_pow(n)` means a^n

GaloisFieldDict gf_gcd(const GaloisFieldDict &o) const; // `a.gf_gcd(o)` returns the gcd of `a` and `o`.
GaloisFieldDict gf_lcm(const GaloisFieldDict &o) const; // `a.gf_lcm(o)` returns the lcm of `a` and `o`.

void gf_div(const GaloisFieldDict &o, const Ptr<GaloisFieldDict> &quo,
                const Ptr<GaloisFieldDict> &rem) const; // a.gf_div(b) represents `a/b`

Documentation and source of the algorithms are given in the module.