BerlekampAlgorithm

Documentation

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

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]

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)

pivotPos'

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

lswap

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

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]]

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

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

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

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

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]

derivPolyZ : derivative of polynmial P over Fp[x]

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

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

irreducibilityTestPolyZ :: Integer -> [Integer] -> Bool

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

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

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

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

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