Optimizing the half-gcd algorithm

2022/12/23 by Joris van der Hoeven, van der Hoeven, Joris · 1 citation
Computer Science · #Polynomial and algebraic computation #Numerical Methods and Algorithms #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.2212.12389

Abstract

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.

Cited by

• Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard

Related

• The Accelerated Euclidean Algorithm
• Bit Complexity of Polynomial GCD on Sparse Representation
• Simple algorithm for GCD of polynomials
• Probably faster multiplication of sparse polynomials
• Nearly Optimal Sparse Polynomial Multiplication