search

konn / computational-algebra

General-Purpose Computer Algebra System as an EDSL in Haskell
http://konn.github.io/computational-algebra/
BSD 3-Clause "New" or "Revised" License
92 stars 9 forks source link

Fixing Integer-polynomial factorisation by Hensel-lifting #6

Closed konn closed 4 years ago

konn commented 4 years ago

Factoring integer-coefficient polynomials by Hensel-lifting (factorHensel) seems not working properly. This pull-request aims at fixing that issue (still in-progress). For example, it cannot factor 4*x^2 - 7*x - 2 into [x - 2,4*x + 1]; it just returns the input as-is.

konn commented 4 years ago

Finally, now all of factorise, factorQBigPrime, and factorHensel works somehow, in a sense that they return all the irreducible factors. But beware: it seems squareFreeDecompFiniteField won't work properly; it sometimes returns not pairwise coprime square-free decomposition. One example is x^8 + x^3 + x^2 + x ∈ 𝔽₂. This bug makes factorise function return duplicated factors: factorise ( x^8 + x^3 + x^2 + x) returns [(x,1),(x + 1,1),(x^4 + x^3 + 1,1),(x + 1,2)], which includes x + 1 twice (although the product coincides with theoriginal input).

We must investigate this to fix this issue.