Optimizing the half-gcd algorithm

Joris van der Hoeven

doi:10.1007/s00200-025-00690-w

Optimizing the half-gcd algorithm

Joris van der Hoeven

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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.

Original language	English
Pages (from-to)	853-877
Number of pages	25
Journal	Applicable Algebra in Engineering, Communication and Computing
Volume	37
Issue number	4
DOIs	https://doi.org/10.1007/s00200-025-00690-w
Publication status	Published - 1 Jul 2026

Keywords

Asymptotic complexity
Discrete Fourier transform
Greatest common divisor
Half-gcd algorithm
Middle product

Access to Document

10.1007/s00200-025-00690-w

Cite this

@article{0a667c86e8df45d59731f411ceb994c6,

title = "Optimizing the half-gcd algorithm",

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.",

keywords = "Asymptotic complexity, Discrete Fourier transform, Greatest common divisor, Half-gcd algorithm, Middle product",

author = "\{van der Hoeven\}, Joris",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2025.",

year = "2026",

month = jul,

day = "1",

doi = "10.1007/s00200-025-00690-w",

language = "English",

volume = "37",

pages = "853--877",

journal = "Applicable Algebra in Engineering, Communication and Computing",

issn = "0938-1279",

publisher = "Springer Science and Business Media Deutschland GmbH",

number = "4",

}

TY - JOUR

T1 - Optimizing the half-gcd algorithm

AU - van der Hoeven, Joris

N1 - Publisher Copyright: © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2025.

PY - 2026/7/1

Y1 - 2026/7/1

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

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

KW - Asymptotic complexity

KW - Discrete Fourier transform

KW - Greatest common divisor

KW - Half-gcd algorithm

KW - Middle product

UR - https://www.scopus.com/pages/publications/105006798871

U2 - 10.1007/s00200-025-00690-w

DO - 10.1007/s00200-025-00690-w

M3 - Article

AN - SCOPUS:105006798871

SN - 0938-1279

VL - 37

SP - 853

EP - 877

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

IS - 4

ER -

Optimizing the half-gcd algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this