GSoC Eighth Week


After completing the work on gf_factor, I moved on to implement Gathen-Shoup’s factorization algorithm. Like Zassenhaus’s agorithm, it is also a probabilistic algorithm.
The paper is available here.

First question: Why this algorithm ?
> Because, it is kind of faster than zassenhaus’s algorithm.

Second question: What is “kind of” here ?
> Well, it is faster when a specific condition satisfies.

Its asymptotic runtime is O(n**2 + n log q).(log n)**2.loglog n, where n is degree of polynomial and q is the field characteristics.
In “Soft O” notation, it is O~(n**2 + n log q). While the cantor zassenhaus’s algorithm has O~(n**2 log q) asymptotic runtime.
So when log q approaches n, the difference is remarkable.

Algorithm Asymptotic Runtime
Shoup O~(n**2)
Zassenhaus O~(n**3)

It also works in three parts, firstly square free factorization, then distinct degree and finally equal degree factorization.
I have completed the implementation of this algorithm on shoup_factorization branch. And also, I changed the container (which stores factors) type to set.
Will send a PR soon.

Written on July 20, 2016