New recombination algorithms for bivariate polynomial factorization based on Hensel lifting

Grégoire Lecerf

doi:10.1007/s00200-010-0121-5

New recombination algorithms for bivariate polynomial factorization based on Hensel lifting

Grégoire Lecerf

Laboratoire de Mathématiques de Versailles

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

Abstract

We present new faster deterministic and probabilistic recombination algorithms to compute the irreducible decomposition of a bivariate polynomial via the classical Hensel lifting technique. For the dense bi-degree polynomial representation, the costs of our recombination algorithms are essentially sub-quadratic.

Original language	English
Pages (from-to)	151-176
Number of pages	26
Journal	Applicable Algebra in Engineering, Communication and Computing
Volume	21
Issue number	2
DOIs	https://doi.org/10.1007/s00200-010-0121-5
Publication status	Published - 1 Jan 2010
Externally published	Yes

Keywords

Hensel lifting
Polynomial factorization

Access to Document

10.1007/s00200-010-0121-5

Cite this

@article{3c6dfd0209314f2e918fa86310e23b92,

title = "New recombination algorithms for bivariate polynomial factorization based on Hensel lifting",

abstract = "We present new faster deterministic and probabilistic recombination algorithms to compute the irreducible decomposition of a bivariate polynomial via the classical Hensel lifting technique. For the dense bi-degree polynomial representation, the costs of our recombination algorithms are essentially sub-quadratic.",

keywords = "Hensel lifting, Polynomial factorization",

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

year = "2010",

month = jan,

day = "1",

doi = "10.1007/s00200-010-0121-5",

language = "English",

volume = "21",

pages = "151--176",

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

issn = "0938-1279",

number = "2",

}

TY - JOUR

T1 - New recombination algorithms for bivariate polynomial factorization based on Hensel lifting

AU - Lecerf, Grégoire

PY - 2010/1/1

Y1 - 2010/1/1

N2 - We present new faster deterministic and probabilistic recombination algorithms to compute the irreducible decomposition of a bivariate polynomial via the classical Hensel lifting technique. For the dense bi-degree polynomial representation, the costs of our recombination algorithms are essentially sub-quadratic.

AB - We present new faster deterministic and probabilistic recombination algorithms to compute the irreducible decomposition of a bivariate polynomial via the classical Hensel lifting technique. For the dense bi-degree polynomial representation, the costs of our recombination algorithms are essentially sub-quadratic.

KW - Hensel lifting

KW - Polynomial factorization

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

U2 - 10.1007/s00200-010-0121-5

DO - 10.1007/s00200-010-0121-5

M3 - Article

AN - SCOPUS:77952012310

SN - 0938-1279

VL - 21

SP - 151

EP - 176

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

IS - 2

ER -

New recombination algorithms for bivariate polynomial factorization based on Hensel lifting

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this