BerlekampAlgorithm- Factorization of polynomials over finite field

Safe HaskellSafe-Inferred




g :: (Eq a, Num a) => Maybe a -> aSource

Berlekamp's Factorization Algorithm over Fp[x] : computes the factorization of a monic square-free polynomial P into irreducible factor polynomials over F_{p}[x] , p is a prime number. This method is based on linear algebra over finite field. | g

frob :: Integer -> Integer -> [Integer] -> [Integer]Source

Frobenius automorphism : linear map V -> V^p - V , V in Fp[x]P and Fp[x]P as vector space over the field Fp.

pivotPos' :: (Eq a, Num a, Num t) => t -> [[a]] -> (Int, t)Source


lswap :: Int -> Int -> ([a], [a1]) -> ([a], [a1])Source


triangulizedModIntegerMat :: Integer -> [[Integer]] -> ([[Integer]], [[Integer]])Source

triangulizedModIntegerMat triangulizedModIntegerMat p m: gives the gauss triangular decomposition of an integeral matrix m in Fp. The result is (r, u) where u is a unimodular matrix, r is an upper-triangular matrix , and u.m = r.

nullSpaceModIntegerMat :: Integer -> [[Integer]] -> [[Integer]]Source

nullSpaceModIntegerMat p m : computes the null space of matrix m in Fp

mmultZ :: Integer -> [[Integer]] -> [[Integer]] -> [[Integer]]Source

mmultZ mmultZ p a b : compute the product of two integer matrices in Fp.

matrixBerlTranspose :: Integer -> [Integer] -> [[Integer]]Source

matrixBerl matrixBerl p f : is the matrix of the Frobenius endomorphism over the canonical base {1,X,X^2..,X^(p-1)} , matrixBerl(i,j) = X^(pj)-X^j mod P.

derivPolyZ :: Integer -> [Integer] -> [Integer]Source

derivPolyZ : derivative of polynmial P over Fp[x]

squareFreePolyZ :: Integer -> [Integer] -> [Integer]Source

squareFreePolyZ squareFreePolyZ p f : gives the euclidean quotient of P and gcd(f,f'). That quotient is a square free polynomial.

irreducibilityTestPolyZ :: Integer -> [Integer] -> BoolSource

irreducibilityTestPolyZ irreducibilityTestPolyZ : irreducibility test of polynomials over Fp[x]

berlekamp :: Integer -> [Integer] -> [[Integer]]Source

berlekamp berlekamp p P: gives a complete factorization of a polynom P of irreducible polynoms over Fp[x].

multPoly :: Integer -> [[Integer]] -> [Integer]Source

multPoly multPoly : product of polynomials P1, .., Pk in Fp[x].