# Fields in SymEngine

##### Clone this wiki locally

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.

`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.