besout 0.1.0.0 → 0.2.0.0
raw patch · 2 files changed
+46/−16 lines, 2 filesdep ~base
Dependency ranges changed: base
Files
- Bezout.hs +44/−14
- besout.cabal +2/−2
Bezout.hs view
@@ -1,17 +1,34 @@-module Bezout(-- * Extended gcd of integers+module Bezout (+-- * Extended gcd of integers besout , -- * Modular inverse of integer-inverseMod,shift,pad,trim,trim' ,deg,(+:),mods,mMod,+inverseMod,+-- * shift+shift,+-- * pad+pad,+-- * trim+trim,+-- * trim'+trim' ,+-- * deg+deg,+-- * (+:)+(+:),+-- * mods+mods,+-- * mMod+mMod, -- * Multiplication of polynomials in F_p[x] multPolyZ, -- * Euclidean division of polynomials for F_p[x]- euclideanPolyMod, +euclideanPolyMod, -- * Extended gcd of polynomials in F_p[x] extendedgcdpoly , -- * Inverse of polynomial P modulo polynomial Q in F_p[x]- inversePolyMod,+inversePolyMod, -- * Pretty form polynom input-prettyFormPoly) where+prettyFormPoly ) where -- besout -- | besout compute extended gcd of two integers. For example : "besout" 13 17 = [4,-3,1] , this means that @@ -28,24 +45,26 @@ inverseMod x y = let a = besout x y in case a!!2 of 1 -> mods (a!!0) y _ -> 0---- | rightpad+-- shift+-- | padding left with n zeros shift n l = l ++ replicate n 0--- | leftpad+-- pad+-- | padding right with n zeros pad n l = replicate n 0 ++ l -- | trim trim x = dropWhile (== 0) x -- | trim' trim' x = let y = trim x in if y == [] then [0] else y -- deg--- | deg +-- | degree of polynomial deg l = length (trim l) - 1 -- | (+:) add or abstract two list of different length (+:) op p q = let d = (length p) - (length q) in zipWith op (pad (-d) p) (pad d q)+-- mods -- | mods return positve remainder of "mod" operator mods :: Integer -> Integer -> Integer mods x p = if y >= 0 then y else y + p where y = mod x p -+-- mMod -- | mMod map "mods" over list of integers mMod :: [Integer]-> Integer ->[Integer] mMod [] _ = []@@ -57,15 +76,21 @@ --To compute the product of polynomials P,Q we borrow the Horner multiplication rules as described by the following chain. --It consists to do n compositions of functions detailed in the following diagramm: --Q -> anxQ + a_(n-1)Q+-- -- R -> xR + a_(n-2)Q+-- -- R -> xR + a_(n-3)Q+-- -- R -> xR + a-1Q+-- -- ...--- R -> xR + a_0Q+--+-- R -> xR + a_0Q+-- --Let f = [2,0,3,2,1::Integer], g = [2,5,-3,1::Integer] in F_7[x]. --"multPolyZ 7 f g" = [4,3,0,0,3,2,6,1] . -- That means that f*g = 4*x^7 + 3*x^6 + 3*x^3 + 2*x^2 + 6*x + 1 in F_7[x].--- Be careful to always use the decreasing order in writing polynoms for multPolyZ .+-- This function require writing polynoms in decreasing order . multPolyZ :: Integer ->[Integer]->[Integer]-> [Integer] multPolyZ _ [0] _ = [0] multPolyZ _ _ [0] = [0]@@ -106,7 +131,9 @@ -- | "extendedgcdpoly" compute the extended gcd of polynomials P and Q in the ring F_p[x] where p is a prime number. -- Let f = [2,0,3,2,1::Integer], g = [2,5,-3,1::Integer] in F_7[x]. -- "extendedgcdpoly" 7 f g = [[5,3],[2,6,5],[2,1]] .--- This means that the gcd of f and g in F_7[x] is the polynom 2*x+1 , and 2*x + 1 = (5*x + 3)*f + (2*x^2 + 6*x + 5)*g in F_7[x].+-- This means that the gcd of f and g in F_7[x] is the polynom 2*x+1 , and+--+-- 2 * x + 1 = (5 * x + 3) * f + (2 * x^2 + 6 * x + 5) * g in F_7[x]. extendedgcdpoly :: Integer -> [Integer] -> [Integer] -> [[Integer]] extendedgcdpoly p x y = let t = besoutPoly p x y in let z = t!!2 in@@ -123,13 +150,16 @@ -- "extendedgcdpoly" 13 f g =[[7,3,7],[6,8,4,7],[1]]. -- So f and g are relatively prime in F_13[x] , and the inverse of f modulo g in F_13[x] is given by -- "inversePolyMod" 13 f g = [7,3,7] . +-- -- Which says that the inverse of ploynomial f denoted f^(-1) is 7*x^2 + 3*x + 7 modulo g in F_13[x] inversePolyMod :: Integer -> [Integer] -> [Integer] -> [Integer] inversePolyMod p x y = let t = extendedgcdpoly p x y in let z = length $ t!!2 in case z of 1 -> t!!0 _ -> [0] -- prettyFormPoly--- | This is a facility for writing non nul terms of polynomial , if f = 5*x^13 + 4*x^5 + (-3)*x^4 + 11*x + 19 , then prettyFormPoly [[5,13],[4,5],[-3,4],[11,1],[19,0]] = [5,0,0,0,0,0,0,0,4,-3,0,0,11,19]+-- | This is a facility for writing non nul terms of polynomial , if f = 5*x^13 + 4*x^5 + (-3)*x^4 + 11*x + 19 , then+--+-- prettyFormPoly [[5,13],[4,5],[-3,4],[11,1],[19,0]] = [5,0,0,0,0,0,0,0,4,-3,0,0,11,19] prettyFormPoly :: [[Integer]]->[Integer] prettyFormPoly [[]] = []
besout.cabal view
@@ -10,7 +10,7 @@ -- PVP summary: +-+------- breaking API changes -- | | +----- non-breaking API additions -- | | | +--- code changes with no API change-version: 0.1.0.0+version: 0.2.0.0 -- A short (one-line) description of the package. synopsis: Extended GCD of polynomials over F_p[x]@@ -50,5 +50,5 @@ -- other-modules: -- Other library packages from which modules are imported.- build-depends: base ==4.5.*+ build-depends: base ==4.6.*