halg-galois-fields-0.6.0.0: General Galois fields, part of halg computational algebra suite.

Safe HaskellNone
LanguageHaskell2010

Algebra.Field.Galois

Synopsis

Documentation

data GF' p (n :: Nat) (f :: Type) Source #

Galois field of order p^n. f stands for the irreducible polynomial over F_p of degree n.

Instances
Reifies p Integer => RightModule Integer (GF' p n f) Source # 
Instance details

Methods

(*.) :: GF' p n f -> Integer -> GF' p n f #

Reifies p Integer => RightModule Natural (GF' p n f) Source # 
Instance details

Methods

(*.) :: GF' p n f -> Natural -> GF' p n f #

Reifies p Integer => LeftModule Integer (GF' p n f) Source # 
Instance details

Methods

(.*) :: Integer -> GF' p n f -> GF' p n f #

Reifies p Integer => LeftModule Natural (GF' p n f) Source # 
Instance details

Methods

(.*) :: Natural -> GF' p n f -> GF' p n f #

Reifies p Integer => Eq (GF' p n f) Source # 
Instance details

Methods

(==) :: GF' p n f -> GF' p n f -> Bool #

(/=) :: GF' p n f -> GF' p n f -> Bool #

(Reifies p Integer, Reifies f (Unipol (F p)), KnownNat n) => Fractional (GF' p n f) Source # 
Instance details

Methods

(/) :: GF' p n f -> GF' p n f -> GF' p n f #

recip :: GF' p n f -> GF' p n f #

fromRational :: Rational -> GF' p n f #

(Reifies p Integer, Reifies f (Unipol (F p)), KnownNat n) => Num (GF' p n f) Source # 
Instance details

Methods

(+) :: GF' p n f -> GF' p n f -> GF' p n f #

(-) :: GF' p n f -> GF' p n f -> GF' p n f #

(*) :: GF' p n f -> GF' p n f -> GF' p n f #

negate :: GF' p n f -> GF' p n f #

abs :: GF' p n f -> GF' p n f #

signum :: GF' p n f -> GF' p n f #

fromInteger :: Integer -> GF' p n f #

(Reifies p Integer, Show (F p)) => Show (GF' p n f) Source # 
Instance details

Methods

showsPrec :: Int -> GF' p n f -> ShowS #

show :: GF' p n f -> String #

showList :: [GF' p n f] -> ShowS #

(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => UFD (GF' p n f) Source # 
Instance details
(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => PID (GF' p n f) Source # 
Instance details

Methods

egcd :: GF' p n f -> GF' p n f -> (GF' p n f, GF' p n f, GF' p n f) #

(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => IntegralDomain (GF' p n f) Source # 
Instance details

Methods

divides :: GF' p n f -> GF' p n f -> Bool #

maybeQuot :: GF' p n f -> GF' p n f -> Maybe (GF' p n f) #

(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => GCDDomain (GF' p n f) Source # 
Instance details

Methods

gcd :: GF' p n f -> GF' p n f -> GF' p n f #

reduceFraction :: GF' p n f -> GF' p n f -> (GF' p n f, GF' p n f) #

lcm :: GF' p n f -> GF' p n f -> GF' p n f #

(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => Euclidean (GF' p n f) Source # 
Instance details

Methods

degree :: GF' p n f -> Maybe Natural #

divide :: GF' p n f -> GF' p n f -> (GF' p n f, GF' p n f) #

quot :: GF' p n f -> GF' p n f -> GF' p n f #

rem :: GF' p n f -> GF' p n f -> GF' p n f #

(KnownNat n, IsGF' p n f) => ZeroProductSemiring (GF' p n f) Source # 
Instance details
(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => ZeroProductSemiring (GF' p n f) Source # 
Instance details
(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => UnitNormalForm (GF' p n f) Source # 
Instance details

Methods

splitUnit :: GF' p n f -> (GF' p n f, GF' p n f) #

(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Ring (GF' p n f) Source # 
Instance details

Methods

fromInteger :: Integer -> GF' p n f

(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Rig (GF' p n f) Source # 
Instance details

Methods

fromNatural :: Natural -> GF' p n f #

(Reifies p Integer, Reifies f (Unipol (F p)), KnownNat n) => Characteristic (GF' p n f) Source # 
Instance details

Methods

char :: proxy (GF' p n f) -> Natural #

(KnownNat n, Reifies p Integer) => DecidableZero (GF' p n f) Source # 
Instance details

Methods

isZero :: GF' p n f -> Bool #

(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => DecidableUnits (GF' p n f) Source # 
Instance details

Methods

recipUnit :: GF' p n f -> Maybe (GF' p n f) #

isUnit :: GF' p n f -> Bool #

(^?) :: Integral n0 => GF' p n f -> n0 -> Maybe (GF' p n f) #

(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => DecidableAssociates (GF' p n f) Source # 
Instance details

Methods

isAssociate :: GF' p n f -> GF' p n f -> Bool #

(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Unital (GF' p n f) Source # 
Instance details

Methods

one :: GF' p n f #

pow :: GF' p n f -> Natural -> GF' p n f #

productWith :: Foldable f0 => (a -> GF' p n f) -> f0 a -> GF' p n f #

(Reifies p Integer, Reifies f (Unipol (F p)), KnownNat n) => Division (GF' p n f) Source # 
Instance details

Methods

recip :: GF' p n f -> GF' p n f #

(/) :: GF' p n f -> GF' p n f -> GF' p n f #

(\\) :: GF' p n f -> GF' p n f -> GF' p n f #

(^) :: Integral n0 => GF' p n f -> n0 -> GF' p n f

(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Commutative (GF' p n f) Source # 
Instance details
(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Semiring (GF' p n f) Source # 
Instance details
(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Multiplicative (GF' p n f) Source # 
Instance details

Methods

(*) :: GF' p n f -> GF' p n f -> GF' p n f #

pow1p :: GF' p n f -> Natural -> GF' p n f #

productWith1 :: Foldable1 f0 => (a -> GF' p n f) -> f0 a -> GF' p n f #

(Reifies p Integer, KnownNat n) => Monoidal (GF' p n f) Source # 
Instance details

Methods

zero :: GF' p n f #

sinnum :: Natural -> GF' p n f -> GF' p n f #

sumWith :: Foldable f0 => (a -> GF' p n f) -> f0 a -> GF' p n f #

(KnownNat n, Reifies p Integer) => Group (GF' p n f) Source # 
Instance details

Methods

(-) :: GF' p n f -> GF' p n f -> GF' p n f #

negate :: GF' p n f -> GF' p n f #

subtract :: GF' p n f -> GF' p n f -> GF' p n f #

times :: Integral n0 => n0 -> GF' p n f -> GF' p n f #

Reifies p Integer => Additive (GF' p n f) Source # 
Instance details

Methods

(+) :: GF' p n f -> GF' p n f -> GF' p n f #

sinnum1p :: Natural -> GF' p n f -> GF' p n f #

sumWith1 :: Foldable1 f0 => (a -> GF' p n f) -> f0 a -> GF' p n f #

Reifies p Integer => Abelian (GF' p n f) Source # 
Instance details
(Reifies p Integer, Show (F p)) => PrettyCoeff (GF' p n f) Source # 
Instance details

Methods

showsCoeff :: Int -> GF' p n f -> ShowSCoeff #

(KnownNat n, IsGF' p n f) => FiniteField (GF' p n f) Source # 
Instance details

Methods

power :: proxy (GF' p n f) -> Natural #

elements :: proxy (GF' p n f) -> [GF' p n f] #

class (KnownNat n, KnownNat p, Reifies f (Unipol (F p))) => IsGF' p n f Source #

Type-constraint synonym to work with Galois field.

Instances
(KnownNat n, KnownNat p, Reifies f (Unipol (F p))) => IsGF' p n (f :: k) Source # 
Instance details

modPoly :: forall p n f. (KnownNat n, Reifies p Integer) => Unipol (F p) -> GF' p n f Source #

modVec :: Sized n (F p) -> GF' p n f Source #

withIrreducible :: forall p a. KnownNat p => Unipol (F p) -> (forall f (n :: Nat). Reifies f (Unipol (F p)) => Proxy (GF' p n f) -> a) -> a Source #

linearRepGF :: GF' p n f -> Vector (F p) Source #

reifyGF' :: MonadRandom m => Natural -> Natural -> (forall (p :: Nat) (f :: Type) (n :: Nat). (Reifies p Integer, Reifies f (Unipol (F p))) => Proxy (GF' p n f) -> a) -> m a Source #

generateIrreducible :: (MonadRandom m, FiniteField k, Eq k) => proxy k -> Natural -> m (Unipol k) Source #

generateIrreducible p n generates irreducible polynomial over F_p of degree n.

withGF' :: MonadRandom m => Natural -> Natural -> (forall (p :: Nat) f (n :: Nat). (Reifies p Integer, Reifies f (Unipol (F p))) => GF' p n f) -> m (Vector Integer) Source #

type GF (p :: Nat) n = GF' p n (Conway p n) Source #

Galois Field of order p^n. This uses conway polynomials as canonical minimal polynomial and it should be known at compile-time (i.e. Reifies (Conway p n) (Unipol (F n)) instances should be defined to use field operations).

class ConwayPolynomial (p :: Nat) (n :: Nat) where Source #

Type-class to provide the dictionary for Conway polynomials

Minimal complete definition

conwayPolynomial

Methods

conwayPolynomial :: proxy p -> proxy n -> Unipol (F p) Source #

Instances
ConwayPolynomial 2 1 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 1 -> Unipol (F 2) Source #

ConwayPolynomial 2 2 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 2 -> Unipol (F 2) Source #

ConwayPolynomial 2 3 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 3 -> Unipol (F 2) Source #

ConwayPolynomial 2 4 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 4 -> Unipol (F 2) Source #

ConwayPolynomial 2 5 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 5 -> Unipol (F 2) Source #

ConwayPolynomial 2 6 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 6 -> Unipol (F 2) Source #

ConwayPolynomial 2 7 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 7 -> Unipol (F 2) Source #

ConwayPolynomial 2 8 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 8 -> Unipol (F 2) Source #

ConwayPolynomial 2 9 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 9 -> Unipol (F 2) Source #

ConwayPolynomial 2 10 Source # 
Instance details

Methods

conwayPolynomial :: proxy 2 -> proxy 10 -> Unipol (F 2) Source #

ConwayPolynomial 3 1 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 1 -> Unipol (F 3) Source #

ConwayPolynomial 3 2 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 2 -> Unipol (F 3) Source #

ConwayPolynomial 3 3 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 3 -> Unipol (F 3) Source #

ConwayPolynomial 3 4 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 4 -> Unipol (F 3) Source #

ConwayPolynomial 3 5 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 5 -> Unipol (F 3) Source #

ConwayPolynomial 3 6 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 6 -> Unipol (F 3) Source #

ConwayPolynomial 3 7 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 7 -> Unipol (F 3) Source #

ConwayPolynomial 3 8 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 8 -> Unipol (F 3) Source #

ConwayPolynomial 3 9 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 9 -> Unipol (F 3) Source #

ConwayPolynomial 3 10 Source # 
Instance details

Methods

conwayPolynomial :: proxy 3 -> proxy 10 -> Unipol (F 3) Source #

ConwayPolynomial 5 1 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 1 -> Unipol (F 5) Source #

ConwayPolynomial 5 2 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 2 -> Unipol (F 5) Source #

ConwayPolynomial 5 3 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 3 -> Unipol (F 5) Source #

ConwayPolynomial 5 4 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 4 -> Unipol (F 5) Source #

ConwayPolynomial 5 5 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 5 -> Unipol (F 5) Source #

ConwayPolynomial 5 6 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 6 -> Unipol (F 5) Source #

ConwayPolynomial 5 7 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 7 -> Unipol (F 5) Source #

ConwayPolynomial 5 8 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 8 -> Unipol (F 5) Source #

ConwayPolynomial 5 9 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 9 -> Unipol (F 5) Source #

ConwayPolynomial 5 10 Source # 
Instance details

Methods

conwayPolynomial :: proxy 5 -> proxy 10 -> Unipol (F 5) Source #

ConwayPolynomial 7 1 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 1 -> Unipol (F 7) Source #

ConwayPolynomial 7 2 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 2 -> Unipol (F 7) Source #

ConwayPolynomial 7 3 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 3 -> Unipol (F 7) Source #

ConwayPolynomial 7 4 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 4 -> Unipol (F 7) Source #

ConwayPolynomial 7 5 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 5 -> Unipol (F 7) Source #

ConwayPolynomial 7 6 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 6 -> Unipol (F 7) Source #

ConwayPolynomial 7 7 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 7 -> Unipol (F 7) Source #

ConwayPolynomial 7 8 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 8 -> Unipol (F 7) Source #

ConwayPolynomial 7 9 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 9 -> Unipol (F 7) Source #

ConwayPolynomial 7 10 Source # 
Instance details

Methods

conwayPolynomial :: proxy 7 -> proxy 10 -> Unipol (F 7) Source #

ConwayPolynomial 11 1 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 1 -> Unipol (F 11) Source #

ConwayPolynomial 11 2 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 2 -> Unipol (F 11) Source #

ConwayPolynomial 11 3 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 3 -> Unipol (F 11) Source #

ConwayPolynomial 11 4 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 4 -> Unipol (F 11) Source #

ConwayPolynomial 11 5 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 5 -> Unipol (F 11) Source #

ConwayPolynomial 11 6 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 6 -> Unipol (F 11) Source #

ConwayPolynomial 11 7 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 7 -> Unipol (F 11) Source #

ConwayPolynomial 11 8 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 8 -> Unipol (F 11) Source #

ConwayPolynomial 11 9 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 9 -> Unipol (F 11) Source #

ConwayPolynomial 11 10 Source # 
Instance details

Methods

conwayPolynomial :: proxy 11 -> proxy 10 -> Unipol (F 11) Source #

data Conway p n Source #

Empty tag to reify Conway polynomial to type-level

Instances
ConwayPolynomial p n => Reifies (Conway p n :: *) (Unipol (F p)) Source # 
Instance details

Methods

reflect :: proxy (Conway p n) -> Unipol (F p)

primitive :: forall p n f. IsGF' p n f => GF' p (n + 1) f Source #

conway :: forall p n. ConwayPolynomial p n => SNat p -> SNat n -> Unipol (F p) Source #

Conway polynomial (if definition is known).

conwayFile :: FilePath -> DecsQ Source #

Parse conway polynomial file and define instances for them. File-format must be the same as Lueback's file.

addConwayPolynomials :: [(Integer, Integer, [Integer])] -> DecsQ Source #

Macro to add Conway polynomials dictionary.