Fast separable factorization and applications

Grégoire Lecerf

doi:10.1007/s00200-008-0062-4

Fast separable factorization and applications

Grégoire Lecerf

Laboratoire de Mathématiques de Versailles

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

Résumé

In this paper we show that the separable decomposition of a univariate polynomial can be computed in softly optimal time, in terms of the number of arithmetic operations in the coefficient field. We also adapt the classical multi-modular strategy that speeds up the computations for many coefficient fields, and we analyze consequences of the new results to the squarefree and the irreducible factorizations.

langue originale	Anglais
Pages (de - à)	135-160
Nombre de pages	26
journal	Applicable Algebra in Engineering, Communication and Computing
Volume	19
Numéro de publication	2
Les DOIs	https://doi.org/10.1007/s00200-008-0062-4
état	Publié - 1 janv. 2008
Modification externe	Oui

Accès au document

10.1007/s00200-008-0062-4

Contient cette citation

@article{f48aafec2cbb475e986283aa7a85d8c3,

title = "Fast separable factorization and applications",

abstract = "In this paper we show that the separable decomposition of a univariate polynomial can be computed in softly optimal time, in terms of the number of arithmetic operations in the coefficient field. We also adapt the classical multi-modular strategy that speeds up the computations for many coefficient fields, and we analyze consequences of the new results to the squarefree and the irreducible factorizations.",

keywords = "Irreducible factorization, Polynomial factorization, Separable factorization, Squarefree factorization",

author = "Gr{\'e}goire Lecerf",

year = "2008",

month = jan,

day = "1",

doi = "10.1007/s00200-008-0062-4",

language = "English",

volume = "19",

pages = "135--160",

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

issn = "0938-1279",

number = "2",

}

TY - JOUR

T1 - Fast separable factorization and applications

AU - Lecerf, Grégoire

PY - 2008/1/1

Y1 - 2008/1/1

N2 - In this paper we show that the separable decomposition of a univariate polynomial can be computed in softly optimal time, in terms of the number of arithmetic operations in the coefficient field. We also adapt the classical multi-modular strategy that speeds up the computations for many coefficient fields, and we analyze consequences of the new results to the squarefree and the irreducible factorizations.

AB - In this paper we show that the separable decomposition of a univariate polynomial can be computed in softly optimal time, in terms of the number of arithmetic operations in the coefficient field. We also adapt the classical multi-modular strategy that speeds up the computations for many coefficient fields, and we analyze consequences of the new results to the squarefree and the irreducible factorizations.

KW - Irreducible factorization

KW - Polynomial factorization

KW - Separable factorization

KW - Squarefree factorization

U2 - 10.1007/s00200-008-0062-4

DO - 10.1007/s00200-008-0062-4

M3 - Article

AN - SCOPUS:41249099838

SN - 0938-1279

VL - 19

SP - 135

EP - 160

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

IS - 2

ER -

Fast separable factorization and applications

Résumé

Accès au document

Empreinte digitale

Contient cette citation