Safe Haskell | None |
---|---|
Language | Haskell2010 |
- factorise :: (MonadRandom m, CoeffRing k, FiniteField k) => Unipol k -> m [(Unipol k, Natural)]
- factorQBigPrime :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer)))
- factorHensel :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer)))
- distinctDegFactor :: forall k. (Eq k, FiniteField k) => Unipol k -> [(Natural, Unipol k)]
- equalDegreeSplitM :: forall k m. (MonadRandom m, CoeffRing k, FiniteField k) => Unipol k -> Natural -> m (Maybe (Unipol k))
- equalDegreeFactorM :: (Eq k, FiniteField k, MonadRandom m) => Unipol k -> Natural -> m [Unipol k]
- henselStep :: (Eq r, Euclidean r) => r -> Unipol r -> Unipol r -> Unipol r -> Unipol r -> Unipol r -> (Unipol r, Unipol r, Unipol r, Unipol r)
- clearDenom :: (CoeffRing a, Euclidean a) => Unipol (Fraction a) -> (a, Unipol a)
- squareFreePart :: (Eq k, FiniteField k) => Unipol k -> Unipol k
- squareFreeDecomp :: (Eq k, Characteristic k, Field k) => Unipol k -> IntMap (Unipol k)
Factorisation
factorise :: (MonadRandom m, CoeffRing k, FiniteField k) => Unipol k -> m [(Unipol k, Natural)] Source #
Factorise a polynomial over finite field using Cantor-Zassenhaus algorithm
factorQBigPrime :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer))) Source #
Factorise the given integer-coefficient polynomial, choosing a large enough prime.
factorHensel :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer))) Source #
Factorise the given interger-coefficient polynomial by Hensel lifting.
Internal helper functions
:: (Eq k, FiniteField k) | |
=> Unipol k | Square-free polynomial over finite field. |
-> [(Natural, Unipol k)] | Distinct-degree decomposition. |
distinctDegFactor f
computes the distinct-degree decomposition of the given
square-free polynomial over finite field f
.
equalDegreeSplitM :: forall k m. (MonadRandom m, CoeffRing k, FiniteField k) => Unipol k -> Natural -> m (Maybe (Unipol k)) Source #
equalDegreeFactorM :: (Eq k, FiniteField k, MonadRandom m) => Unipol k -> Natural -> m [Unipol k] Source #
:: (Eq r, Euclidean r) | |
=> r | modulus |
-> Unipol r | |
-> Unipol r | |
-> Unipol r | |
-> Unipol r | |
-> Unipol r | |
-> (Unipol r, Unipol r, Unipol r, Unipol r) |
Given that f = gh (mod m)
with sg + th = 1 (mod m)
and leadingCoeff f
isn't zero divisor mod m,
henselStep m f g h s t
calculates the unique (g', h', s', t') s.t.
f = g' h' (mod m^2), g' = g (mod m), h' = h (mod m), s' = s (mod m), t' = t (mod m)
, h'
monic.
squareFreePart :: (Eq k, FiniteField k) => Unipol k -> Unipol k Source #
squareFreeDecomp :: (Eq k, Characteristic k, Field k) => Unipol k -> IntMap (Unipol k) Source #