Polynomial factorisation

[Bodigrim]

Some inspiration might be found in http://hackage.haskell.org/package/toysolver-0.6.0/docs/ToySolver-Data-Polynomial.html#t:Factor

[MathiasBartl]

I was into cryptography, maybe I could do this, if CarlEdman wants to do Thue equations.

[Bodigrim]

Cool :)

---

Another possible source of inspiration is http://hackage.haskell.org/package/computational-algebra-0.5.0.0/docs/Algebra-Ring-Polynomial-Factorise.html
But I would like it to be implemented as instance UniqueFactorisation for Data.Poly.Poly.

[MathiasBartl]

So what do you want, that these packages don't already implement?

[Bodigrim]

A better API, I guess, and a better interaction with other packages. With all due respect, both toysolver and computational-algebra are pretty monstrous packages with tons of dependencies.

Looking at Algebra.Ring.Polynomial.Factorise I see:

factorQBigPrime :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer)))
factorHensel    :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer))) 

Not only I have no idea what is the practical difference between these functions, but return types also do not make any sense to me - does not look like a factorisation at all.

ToySolver.Data.Polynomial.Factor looks less intimidating, but its choice of data structures and dependencies means that performance is wanting. Map-based implementation for dense univariate polynomials is sub-par; primes coming from a lazy wheel sieve are cute, but slow; modular arithmetic can be implemented much faster, etc.

(The fierce critics above does not mean that I don't like these packages - quite contrary, these are fantastic ones and a pinnacle of engineering in many aspects. They just do not fit my particular purposes and requirements)

---

Ideally I would like to have several instances of form

instance UniqueFactorisation (Data.Poly.VPoly a)

for some suitable as. Implementing a ~ Integer would be a good start already ;)

I suggest using polynomials from poly, modular arithmetic from mod and primes from arithmoi itself.

[MathiasBartl]

That sounds like the best would be modifying an existing function.

[Bodigrim]

Ideally - yes, but I do not foresee this happening. IMO it is less work to add polynomial factorisation to arithmoi than inject all desired improvements into toysolver. Also it is unviable for arithmoi to depend on toysolver.

[MathiasBartl]

So Polynomials over the integers or over finite fields?

[Bodigrim]

Polynomials over integers, but AFAIR their factorisation would require factorisation of polynomials over Mod p as well.

[MathiasBartl]

So I could start with implementing Cantor-Zassenhaus.

[Bodigrim]

Yes, absolutely.

[MathiasBartl]

Most specifically I would need an GCD algorithm first.

[Bodigrim]

It’s available from https://hackage.haskell.org/package/semirings-0.5.3/docs/Data-Euclidean.html#v:gcd