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.
log q approaches
n, the difference is remarkable.
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
Will send a PR soon.