Safe Haskell	None
Language	Haskell2010

Algebra.Field.Galois

Synopsis

data GF' p (n :: Nat) (f :: Type)
class (KnownNat n, KnownNat p, Reifies f (Unipol (F p))) => IsGF' 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 :: Nat). 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 :: Nat) (f :: Type) (n :: Nat). (Reifies p Integer, Reifies f (Unipol (F p))) => Proxy (GF' p n f) -> a) -> m a
generateIrreducible :: (MonadRandom m, Random k, FiniteField k, Eq k) => proxy k -> Natural -> m (Unipol k)
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)
type GF (p :: Nat) n = GF' p n (Conway p n)
class ConwayPolynomial (p :: Nat) (n :: Nat) where
- conwayPolynomial :: proxy p -> proxy n -> Unipol (F p)
data Conway p n
primitive :: forall p n. (IsGF' p n (Conway p n), 1 <= n) => GF p n
primitive' :: forall p n f. (IsGF' p n f, 1 <= n) => GF' p n f
conway :: forall p n. ConwayPolynomial p n => SNat p -> SNat n -> Unipol (F p)
conwayFile :: FilePath -> DecsQ
addConwayPolynomials :: [(Integer, Integer, [Integer])] -> DecsQ

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

Instances details

Reifies p Integer => RightModule Integer (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods (*.) :: GF' p n f -> Integer -> GF' p n f #
Reifies p Integer => RightModule Natural (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods (*.) :: GF' p n f -> Natural -> GF' p n f #
Reifies p Integer => LeftModule Integer (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods (.*) :: Integer -> GF' p n f -> GF' p n f #
Reifies p Integer => LeftModule Natural (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods (.*) :: Natural -> GF' p n f -> GF' p n f #
Reifies p Integer => Eq (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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, KnownNat n, Show (F p)) => Show (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois
(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => PID (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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))) => GCDDomain (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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))) => IntegralDomain (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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))) => Euclidean (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois
(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => ZeroProductSemiring (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois
(KnownNat n, Reifies p Integer, Reifies f (Unipol (F p))) => UnitNormalForm (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois Methods char :: proxy (GF' p n f) -> Natural #
(KnownNat n, Reifies p Integer) => DecidableZero (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois
(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Semiring (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois
(KnownNat n, Reifies f (Unipol (F p)), Reifies p Integer) => Multiplicative (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois 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 Defined in Algebra.Field.Galois
NFData (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods rnf :: GF' p n f -> () #
(Reifies p Integer, KnownNat n, Show (F p)) => PrettyCoeff (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods showsCoeff :: Int -> GF' p n f -> ShowSCoeff #
(KnownNat n, IsGF' p n f) => FiniteField (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods power :: proxy (GF' p n f) -> Natural # elements :: proxy (GF' p n f) -> [GF' p n f] #
IsGF' p n f => Random (GF' p n f) Source #
Instance details Defined in Algebra.Field.Galois Methods randomR :: RandomGen g => (GF' p n f, GF' p n f) -> g -> (GF' p n f, g) random :: RandomGen g => g -> (GF' p n f, g) randomRs :: RandomGen g => (GF' p n f, GF' p n f) -> g -> [GF' p n f] randoms :: RandomGen g => g -> [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

Instances details

(KnownNat n, KnownNat p, Reifies f (Unipol (F p))) => IsGF' p n (f :: k) Source #
Instance details Defined in Algebra.Field.Galois

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 #

linearRepGF' :: GF' p n f -> Vector Integer 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, Random k, 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

Methods

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

Instances

Instances details

ConwayPolynomial 2 1 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 1 -> Unipol (F 2) Source #
ConwayPolynomial 2 2 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 2 -> Unipol (F 2) Source #
ConwayPolynomial 2 3 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 3 -> Unipol (F 2) Source #
ConwayPolynomial 2 4 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 4 -> Unipol (F 2) Source #
ConwayPolynomial 2 5 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 5 -> Unipol (F 2) Source #
ConwayPolynomial 2 6 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 6 -> Unipol (F 2) Source #
ConwayPolynomial 2 7 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 7 -> Unipol (F 2) Source #
ConwayPolynomial 2 8 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 8 -> Unipol (F 2) Source #
ConwayPolynomial 2 9 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 9 -> Unipol (F 2) Source #
ConwayPolynomial 2 10 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 2 -> proxy 10 -> Unipol (F 2) Source #
ConwayPolynomial 3 1 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 1 -> Unipol (F 3) Source #
ConwayPolynomial 3 2 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 2 -> Unipol (F 3) Source #
ConwayPolynomial 3 3 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 3 -> Unipol (F 3) Source #
ConwayPolynomial 3 4 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 4 -> Unipol (F 3) Source #
ConwayPolynomial 3 5 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 5 -> Unipol (F 3) Source #
ConwayPolynomial 3 6 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 6 -> Unipol (F 3) Source #
ConwayPolynomial 3 7 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 7 -> Unipol (F 3) Source #
ConwayPolynomial 3 8 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 8 -> Unipol (F 3) Source #
ConwayPolynomial 3 9 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 9 -> Unipol (F 3) Source #
ConwayPolynomial 3 10 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 3 -> proxy 10 -> Unipol (F 3) Source #
ConwayPolynomial 5 1 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 1 -> Unipol (F 5) Source #
ConwayPolynomial 5 2 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 2 -> Unipol (F 5) Source #
ConwayPolynomial 5 3 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 3 -> Unipol (F 5) Source #
ConwayPolynomial 5 4 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 4 -> Unipol (F 5) Source #
ConwayPolynomial 5 5 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 5 -> Unipol (F 5) Source #
ConwayPolynomial 5 6 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 6 -> Unipol (F 5) Source #
ConwayPolynomial 5 7 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 7 -> Unipol (F 5) Source #
ConwayPolynomial 5 8 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 8 -> Unipol (F 5) Source #
ConwayPolynomial 5 9 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 9 -> Unipol (F 5) Source #
ConwayPolynomial 5 10 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 5 -> proxy 10 -> Unipol (F 5) Source #
ConwayPolynomial 7 1 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 1 -> Unipol (F 7) Source #
ConwayPolynomial 7 2 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 2 -> Unipol (F 7) Source #
ConwayPolynomial 7 3 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 3 -> Unipol (F 7) Source #
ConwayPolynomial 7 4 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 4 -> Unipol (F 7) Source #
ConwayPolynomial 7 5 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 5 -> Unipol (F 7) Source #
ConwayPolynomial 7 6 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 6 -> Unipol (F 7) Source #
ConwayPolynomial 7 7 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 7 -> Unipol (F 7) Source #
ConwayPolynomial 7 8 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 8 -> Unipol (F 7) Source #
ConwayPolynomial 7 9 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 9 -> Unipol (F 7) Source #
ConwayPolynomial 7 10 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 7 -> proxy 10 -> Unipol (F 7) Source #
ConwayPolynomial 11 1 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 1 -> Unipol (F 11) Source #
ConwayPolynomial 11 2 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 2 -> Unipol (F 11) Source #
ConwayPolynomial 11 3 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 3 -> Unipol (F 11) Source #
ConwayPolynomial 11 4 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 4 -> Unipol (F 11) Source #
ConwayPolynomial 11 5 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 5 -> Unipol (F 11) Source #
ConwayPolynomial 11 6 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 6 -> Unipol (F 11) Source #
ConwayPolynomial 11 7 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 7 -> Unipol (F 11) Source #
ConwayPolynomial 11 8 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 8 -> Unipol (F 11) Source #
ConwayPolynomial 11 9 Source #
Instance details Defined in Algebra.Field.Galois.Conway Methods conwayPolynomial :: proxy 11 -> proxy 9 -> Unipol (F 11) Source #
ConwayPolynomial 11 10 Source #
Instance details Defined in Algebra.Field.Galois.Conway 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

Instances details

ConwayPolynomial p n => Reifies (Conway p n :: Type) (Unipol (F p)) Source #
Instance details Defined in Algebra.Field.Galois.Internal Methods reflect :: proxy (Conway p n) -> Unipol (F p)

primitive :: forall p n. (IsGF' p n (Conway p n), 1 <= n) => GF p n Source #

primitive' :: forall p n f. (IsGF' p n f, 1 <= n) => GF' p n 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.