Lifting and recombination techniques for absolute factorization (Q2371310): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: Magma / rank | |||
Normal rank |
Revision as of 23:30, 28 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lifting and recombination techniques for absolute factorization |
scientific article |
Statements
Lifting and recombination techniques for absolute factorization (English)
0 references
4 July 2007
0 references
Given a field \(K\) the authors consider the problem of factoring bivariate polynomials \(F\) of the polynomial ring \(K[x,y]\) over the algebraic closure \(\overline{K}\) (``absolute factorization''). The ground field \(K\) must have a characteristic zero or one larger than \(d(d-1)+1\), where \(d\) denotes the total degree of \(F\). They further assume that \(F\) is square-free and that for each integer \(d\) a computation tree is given that computes the product of two univariate polynomials of degree at most \(d\) with at most \(M(d)\) operations, independently of the base ring. Improving known results they develop an algorithm which provides the absolute factorization of \(F\) in \(O(d^3 M(d) \log (d))\) arithmetic operations in \(K\). For a test whether \(F\) is absolutely irreducible they get slightly better bounds. The authors also develop probabilistic methods for absolute factorization.
0 references
absolute factorization
0 references
bivariate polynomials
0 references