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