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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

1 Citation (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	853-877
Nombre de pages	25
journal	Applicable Algebra in Engineering, Communication and Computing
Volume	37
Numéro de publication	4
Les DOIs	https://doi.org/10.1007/s00200-025-00690-w
état	Publié - 1 juil. 2026

Accès au document

10.1007/s00200-025-00690-w

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@article{0a667c86e8df45d59731f411ceb994c6,

title = "Optimizing the half-gcd algorithm",

abstract = "In this paper, we propose a carefully optimized {\textquotedblleft}half-gcd{\textquotedblright} 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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation