I have been selected for GSoC’16 to work with Sympy on Implementing Finite Fields and Set module in SymEngine.

SymEngine is a standalone fast C++ symbolic manipulation library.

About the Proposal

We all know that Polynomial factorization is one of the fundamental tools of the computer algebra systems. And in symbolic mathematics, it is one of the basic requirement over which other algorithms can be implemented.
Currently, SymEngine has the implementation of Univariate Polynomial class, which provides us the basic functionality to add, multiply and subtract two polynomials.
Now, comes the problem of factoring the polynomials.
We have explicit solution formulas only till polynomials of degree four(the Quadtratic formula for degree 2, the Cardano formulas for third-degree equations, and the Ferrari formula for degree 4).
For sure, we need a different way out for higher degree polynomials. We see that there are algorithms for factorization in finite fields:

• Cantor–Zassenhaus algorithm
• Berlekamp’s algorithm

So, this summers I will be working on converting a polynomial in integer field to finite field, then factorizing them. After which we have to do Hensel Lifting to bring back the factored polynomial to integer field.

Furthermore, I will be working on implementing Sets module. These two together will help us to create a basic infrastructure over which we can develop a solvers module in SymEngine.

My proposal can be found here.

Community Bonding Period

I have been alloted Isuru Fernando, Thilina Rathnayake, Sumith and Ondřej Čertík as mentors.
The SymEngine community is very fast in reachability. We had a discussion on gitter channel of SymEngine, about the proceedings of our Proposals. As SymEngine has an implementaion of sparse polynomials, I will be working on changing them to Finite Fields. Like:

GaloisField::GaloisField(std::map<unsigned, int> &dict, unsigned modulo) : modulo_(modulo)
{
	unsigned temp;
	for (auto iter : dict) {
		temp = iter.second % modulo;
		if (temp != 0)
			dict_[iter.first] = temp;
	}
}

where dict is the dictionary of Univariate Polynomial representation and, dict_ stores its finite field representation modulo modulo_. I will be implementing this in the first week of GSoC period.

Work already Done

During the Community Bonding Period, I worked on implementing UniversalSet and FiniteSet.
UniversalSet is a singleton class like EmptySet, and while implementing this I learned a lot about Singleton classes.
FiniteSet is a class with a set of RCP<const Basic> as member variable. It can contain any object of Basic type. While implemeting this, we came on a fix over what to do when we have a interval like [1, 1], i.e. both end points equal. This led to a little change in Interval’s code, and now it returns a FiniteSet. Though this PR is not merged till now. I hope to get it merged in the next few days and along with it keep working on Finite Field implementation.