| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Algebra.Ring.Polynomial.Factorise
Synopsis
- factorise :: (MonadRandom m, CoeffRing k, FiniteField k, Random 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)))
- isReducible :: forall k. (FiniteField k, Eq k) => Unipol k -> Bool
- distinctDegFactor :: forall k. (Eq k, FiniteField k) => Unipol k -> [(Natural, Unipol k)]
- equalDegreeSplitM :: forall k m. (MonadRandom m, Random k, CoeffRing k, FiniteField k) => Unipol k -> Natural -> m (Maybe (Unipol k))
- equalDegreeFactorM :: (Eq k, FiniteField k, MonadRandom m, Random k) => 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)
- multiHensel :: Natural -> Int -> Unipol Integer -> [Unipol Integer] -> [Unipol Integer]
- clearDenom :: (CoeffRing a, Euclidean a) => Unipol (Fraction a) -> (a, Unipol a)
- squareFreePart :: (Eq k, FiniteField k) => Unipol k -> Unipol k
- pthRoot :: forall r. (CoeffRing r, FiniteField r) => Unipol r -> Unipol r
- yun :: (CoeffRing r, Field r) => Unipol r -> IntMap (Unipol r)
- squareFreeDecompFiniteField :: (Eq k, FiniteField k) => Unipol k -> IntMap (Unipol k)
Factorisation
factorise :: (MonadRandom m, CoeffRing k, FiniteField k, Random 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 primitive and square-freeinteger-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.
isReducible :: forall k. (FiniteField k, Eq k) => Unipol k -> Bool Source #
Reducibility test for univariate polynomials over finite fields.
Internal helper functions
Arguments
| :: forall k. (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, Random k, CoeffRing k, FiniteField k) => Unipol k -> Natural -> m (Maybe (Unipol k)) Source #
equalDegreeFactorM :: (Eq k, FiniteField k, MonadRandom m, Random k) => Unipol k -> Natural -> m [Unipol k] Source #
Arguments
| :: (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.
Arguments
| :: Natural | prime |
| -> Int | iteration count |
| -> Unipol Integer | original polynomial |
| -> [Unipol Integer] | monic coprime factorisation mod |
| -> [Unipol Integer] | coprime factorisation mod |
Monic hensel lifting for many factors.
squareFreePart :: (Eq k, FiniteField k) => Unipol k -> Unipol k Source #
yun :: (CoeffRing r, Field r) => Unipol r -> IntMap (Unipol r) Source #
Yun's method to compute square-free decomposition of a univariate polynomial over field of characteristic \(0\).
Use squareFreeDecompFiniteField for finite fields.
squareFreeDecompFiniteField :: (Eq k, FiniteField k) => Unipol k -> IntMap (Unipol k) Source #
Square-free decomposition of polynomials over a finite field.
Use yun for a polynomials over a field of characteristic zero.