The Tangent-Graeffe root finding algorithm

Abstract: Let $f(x)$ be a polynomial of degree $d$ over a prime field of size $p$. Suppose $f(x)$ has $d$ distinct roots in the field and we want to compute them. Question: How fast can we compute the roots?

The most well known method is the Cantor-Zassenhaus algorithm from 1981. It is implemented in Maple and Magma. It does, on average, $O(M(d) \log d \log p)$ arithmetic operations in the field where $M(d)$ is the cost of multiplying two polynomials of degree $\le d$.

In 2015 Grenet, van der Hoeven and Lecerf found a beautiful new method for the case $p = s 2^k + 1$ with $s \in O(d)$. The new method improves on Cantor-Zassenhaus by a factor of $O(\log d)$. Our contribution is a speed up for the core computation of the new method by a constant factor and a C implementation of the new method using asymptotically fast polynomial arithmetic.

In the talk I will present the main ideas behind the new Tangent-Graeffe algorithm, some timings comparing the Tangent Graeffe algorithm with the Cantor-Zassenhaus algorithm in Magma, and a new polynomial factorization world record.

This is joint work with Joris van der Hoeven.

algebraic geometrynumber theory

Audience: researchers in the topic

---

SFU NT-AG seminar

Series comments: Description: Research/departmental seminar

Seminar usually meets in-person. For online editions, the Zoom link is shared via mailing list.

---