Optimizing the half-gcd algorithm

12/23/2022
by   Joris van der Hoeven, et al.
0

In this paper, we propose a carefully optimized "half-gcd" algorithm for polynomials. We achieve a constant speed-up with respect to previous work for the asymptotic time complexity. We also discuss special optimizations that are possible when polynomial multiplication is done using radix two FFTs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset