Open Bodigrim opened 4 years ago
I was into cryptography, maybe I could do this, if CarlEdman wants to do Thue equations.
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
.
So what do you want, that these packages don't already implement?
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 a
s. Implementing a ~ Integer
would be a good start already ;)
I suggest using polynomials from poly
, modular arithmetic from mod
and primes from arithmoi
itself.
That sounds like the best would be modifying an existing function.
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
.
So Polynomials over the integers or over finite fields?
Polynomials over integers, but AFAIR their factorisation would require factorisation of polynomials over Mod p
as well.
So I could start with implementing Cantor-Zassenhaus.
Yes, absolutely.
Most specifically I would need an GCD algorithm first.
I assume that there is no real objection to using the Math.Polynomial package? http://hackage.haskell.org/package/polynomial-0.7.3/docs/Math-Polynomial.html
Except that Math.Polynomial
does not compile against four last versions of GHC? ;)
Is something missing from poly, which I suggested above?
Some inspiration might be found in http://hackage.haskell.org/package/toysolver-0.6.0/docs/ToySolver-Data-Polynomial.html#t:Factor