Algebra.Field.Galois

Documentation

data GF' p n f

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

Instances

Reifies k p Integer => LeftModule Integer (GF' k p n f)

Methods

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

Reifies k p Integer => LeftModule Natural (GF' k p n f)

Methods

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

Reifies k p Integer => RightModule Integer (GF' k p n f)

Methods

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

Reifies k p Integer => RightModule Natural (GF' k p n f)

Methods

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

Reifies k p Integer => Eq (GF' k p n f)

Methods

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

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

(Reifies k p Integer, Reifies * f (Unipol (F k p)), KnownNat n) => Fractional (GF' k p n f)

Methods

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

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

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

(Reifies k p Integer, Reifies * f (Unipol (F k p)), KnownNat n) => Num (GF' k p n f)

Methods

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

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

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

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

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

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

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

(Reifies k p Integer, Show (F k p)) => Show (GF' k p n f)

Methods

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

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

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

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => IntegralDomain (GF' k p n f)

Methods

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

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

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => GCDDomain (GF' k p n f)

Methods

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

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

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

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => UFD (GF' k p n f)

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => PID (GF' k p n f)

Methods

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

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => Euclidean (GF' k p n f)

Methods

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

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

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

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

(KnownNat n, Reifies * f (Unipol (F k p)), Reifies k p Integer) => Commutative (GF' k p n f)

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => UnitNormalForm (GF' k p n f)

Methods

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

(KnownNat n, IsGF' * p n f) => ZeroProductSemiring (GF' Nat p n f)

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => ZeroProductSemiring (GF' k p n f)

(KnownNat n, Reifies * f (Unipol (F k p)), Reifies k p Integer) => Ring (GF' k p n f)

Methods

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

(Reifies k p Integer, Reifies * f (Unipol (F k p)), KnownNat n) => Characteristic (GF' k p n f)

Methods

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

(KnownNat n, Reifies * f (Unipol (F k p)), Reifies k p Integer) => Rig (GF' k p n f)

Methods

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

(KnownNat n, Reifies k p Integer) => DecidableZero (GF' k p n f)

Methods

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

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => DecidableUnits (GF' k p n f)

Methods

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

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

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

(KnownNat n, Reifies k p Integer, Reifies * f (Unipol (F k p))) => DecidableAssociates (GF' k p n f)

Methods

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

(Reifies k p Integer, Reifies * f (Unipol (F k p)), KnownNat n) => Division (GF' k p n f)

Methods

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

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

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

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

(KnownNat n, Reifies * f (Unipol (F k p)), Reifies k p Integer) => Unital (GF' k p n f)

Methods

one :: GF' k p n f

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

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

(KnownNat n, Reifies k p Integer) => Group (GF' k p n f)

Methods

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

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

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

times :: Integral n => n -> GF' k p n f -> GF' k p n f

(KnownNat n, Reifies * f (Unipol (F k p)), Reifies k p Integer) => Multiplicative (GF' k p n f)

Methods

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

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

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

(KnownNat n, Reifies * f (Unipol (F k p)), Reifies k p Integer) => Semiring (GF' k p n f)

(Reifies k p Integer, KnownNat n) => Monoidal (GF' k p n f)

Methods

zero :: GF' k p n f

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

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

Reifies k p Integer => Additive (GF' k p n f)

Methods

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

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

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

Reifies k p Integer => Abelian (GF' k p n f)

(Reifies k p Integer, Show (F k p)) => PrettyCoeff (GF' k p n f)

Methods

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

(KnownNat n, IsGF' * p n f) => FiniteField (GF' Nat p n f)

Methods

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

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

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

Type-constraint synonym to work with Galois field.

Instances

(KnownNat n, KnownNat p, Reifies k f (Unipol (F Nat p))) => IsGF' k p n f

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

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

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

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

linearRepGF' :: GF' p n f -> Vector Integer

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

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

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

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

type GF p n = GF' p n (Conway p n)

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 n where

Type-class to provide the dictionary for Conway polynomials

Minimal complete definition

conwayPolynomial

Methods

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

data Conway p n

Empty tag to reify Conway polynomial to type-level

Instances

ConwayPolynomial p n => Reifies * (Conway Nat Nat p n) (Unipol (F Nat p))

Methods

reflect :: proxy (Unipol (F Nat p)) -> a

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

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

Conway polynomial (if definition is known).

conwayFile :: FilePath -> DecsQ

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

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

Macro to add Conway polynomials dictionary.