Safe Haskell | None |
---|---|
Language | Haskell2010 |
An efficient implementation of Galois fields used in cryptography research.
Synopsis
- class (Arbitrary k, Field k, Fractional k, Generic k, Group k, NFData k, Ord k, Pretty k, Random k, Show k) => GaloisField k where
- pow :: (GaloisField k, Integral n) => k -> n -> k
- data Prime (p :: Nat)
- class GaloisField k => PrimeField k
- fromP :: PrimeField k => k -> Integer
- toP :: KnownNat p => Integer -> Prime p
- toP' :: KnownNat p => Integer -> Prime p
- data Extension p k
- class GaloisField k => ExtensionField k
- class GaloisField k => IrreducibleMonic p k where
- fromE :: (ExtensionField k, GaloisField l, IrreducibleMonic p l, k ~ Extension p l) => k -> [l]
- conj :: IrreducibleMonic p k => Extension p k -> Extension p k
- toE :: forall k p. IrreducibleMonic p k => [k] -> Extension p k
- toE' :: forall k p. IrreducibleMonic p k => [k] -> Extension p k
- pattern U :: IrreducibleMonic p k => Extension p k
- pattern U2 :: IrreducibleMonic p k => Extension p k
- pattern U3 :: IrreducibleMonic p k => Extension p k
- pattern V :: IrreducibleMonic p k => k -> Extension p k
- pattern X :: GaloisField k => VPoly k
- pattern X2 :: GaloisField k => VPoly k
- pattern X3 :: GaloisField k => VPoly k
- pattern Y :: IrreducibleMonic p k => VPoly k -> VPoly (Extension p k)
- data Binary (p :: Nat)
- class GaloisField k => BinaryField k
- fromB :: BinaryField k => k -> Integer
- toB :: KnownNat p => Integer -> Binary p
- toB' :: KnownNat p => Integer -> Binary p
- qnr :: GaloisField k => Maybe k
- qr :: GaloisField k => k -> Bool
- quad :: GaloisField k => k -> k -> k -> Maybe k
- rnd :: (GaloisField k, MonadRandom m) => m k
- rndR :: (GaloisField k, MonadRandom m) => (k, k) -> m k
- sr :: GaloisField k => k -> Maybe k
- class (GaloisField k, GaloisField l) => TowerOfFields k l where
- embed :: k -> l
- (*^) :: TowerOfFields k l => k -> l -> l
- class Group g => CyclicSubgroup g where
- gen :: g
- data RootsOfUnity (n :: Nat) k
- cardinality :: forall n k. (KnownNat n, GaloisField k) => RootsOfUnity n k -> Natural
- cofactor :: forall n k. (KnownNat n, GaloisField k) => RootsOfUnity n k -> Natural
- isPrimitiveRootOfUnity :: (KnownNat n, GaloisField k) => RootsOfUnity n k -> Bool
- isRootOfUnity :: (KnownNat n, GaloisField k) => RootsOfUnity n k -> Bool
- toU :: forall n k. (KnownNat n, GaloisField k) => k -> RootsOfUnity n k
- toU' :: forall n k. (KnownNat n, GaloisField k) => k -> RootsOfUnity n k
Galois fields
class (Arbitrary k, Field k, Fractional k, Generic k, Group k, NFData k, Ord k, Pretty k, Random k, Show k) => GaloisField k where Source #
Galois fields GF(p^q)
for p
prime and q
non-negative.
Characteristic p
of field and order of prime subfield.
Degree q
of field as extension field over prime subfield.
Frobenius endomorphism x -> x^p
of prime subfield.
order :: k -> Natural Source #
Order p^q
of field.
Instances
KnownNat p => GaloisField (Binary p) Source # | |
KnownNat p => GaloisField (Prime p) Source # | |
IrreducibleMonic p k => GaloisField (Extension p k) Source # | |
pow :: (GaloisField k, Integral n) => k -> n -> k Source #
Exponentiation of field element to integer.
Prime fields
data Prime (p :: Nat) Source #
Prime field elements.
Instances
class GaloisField k => PrimeField k Source #
Prime fields GF(p) = Z/pZ
for p
prime.
fromP :: PrimeField k => k -> Integer Source #
Convert from GF(p)
to Z
.
Extension fields
Extension field elements.
Instances
class GaloisField k => ExtensionField k Source #
Extension fields GF(p^q)[X]/<f(X)>
for p
prime, q
positive, and
f(X)
irreducible monic in GF(p^q)[X]
.
Instances
IrreducibleMonic p k => ExtensionField (Extension p k) Source # | |
Defined in Data.Field.Galois.Extension fromE :: (GaloisField l, IrreducibleMonic p0 l, Extension p k ~ Extension p0 l) => Extension p k -> [l] Source # |
class GaloisField k => IrreducibleMonic p k where Source #
Irreducible monic polynomial f(X)
of extension field.
fromE :: (ExtensionField k, GaloisField l, IrreducibleMonic p l, k ~ Extension p l) => k -> [l] Source #
Convert from GF(p^q)[X]/<f(X)>
to GF(p^q)[X]
.
conj :: IrreducibleMonic p k => Extension p k -> Extension p k Source #
Complex conjugation a+bi -> a-bi
of quadratic extension field.
toE :: forall k p. IrreducibleMonic p k => [k] -> Extension p k Source #
Safe convert from GF(p^q)[X]
to GF(p^q)[X]/<f(X)>
.
toE' :: forall k p. IrreducibleMonic p k => [k] -> Extension p k Source #
Unsafe convert from GF(p^q)[X]
to GF(p^q)[X]/<f(X)>
.
pattern U :: IrreducibleMonic p k => Extension p k Source #
Pattern for field element U
.
pattern U2 :: IrreducibleMonic p k => Extension p k Source #
Pattern for field element U^2
.
pattern U3 :: IrreducibleMonic p k => Extension p k Source #
Pattern for field element U^3
.
pattern V :: IrreducibleMonic p k => k -> Extension p k Source #
Pattern for descending tower of indeterminate variables for field elements.
pattern X :: GaloisField k => VPoly k Source #
Pattern for monic monomial X
.
pattern X2 :: GaloisField k => VPoly k Source #
Pattern for monic monomial X^2
.
pattern X3 :: GaloisField k => VPoly k Source #
Pattern for monic monomial X^3
.
pattern Y :: IrreducibleMonic p k => VPoly k -> VPoly (Extension p k) Source #
Pattern for descending tower of indeterminate variables for monic monomials.
Binary fields
data Binary (p :: Nat) Source #
Binary field elements.
Instances
class GaloisField k => BinaryField k Source #
Binary fields GF(2^q)[X]/<f(X)>
for q
positive and
f(X)
irreducible monic in GF(2^q)[X]
encoded as an integer.
fromB :: BinaryField k => k -> Integer Source #
Convert from GF(2^q)[X]/<f(X)>
to Z
.
Square roots
qnr :: GaloisField k => Maybe k Source #
Get randomised quadratic nonresidue.
qr :: GaloisField k => k -> Bool Source #
Check if quadratic residue.
quad :: GaloisField k => k -> k -> k -> Maybe k Source #
Solve quadratic ax^2 + bx + c = 0
over field.
rnd :: (GaloisField k, MonadRandom m) => m k Source #
Randomised field element.
rndR :: (GaloisField k, MonadRandom m) => (k, k) -> m k Source #
Randomised field element in range.
sr :: GaloisField k => k -> Maybe k Source #
Square root of field element.
Towers of fields
class (GaloisField k, GaloisField l) => TowerOfFields k l where Source #
Tower of fields L
over K
strict partial ordering.
Instances
(TowerOfFields k l, IrreducibleMonic p l, TowerOfFields l (Extension p l)) => TowerOfFields k (Extension p l) Source # | |
Defined in Data.Field.Galois.Tower | |
IrreducibleMonic p k => TowerOfFields k (Extension p k) Source # | |
Defined in Data.Field.Galois.Tower | |
KnownNat p => TowerOfFields (Binary p) (Binary p) Source # | |
KnownNat p => TowerOfFields (Prime p) (Prime p) Source # | |
KnownNat p => TowerOfFields (Prime 2) (Binary p) Source # | |
IrreducibleMonic p k => TowerOfFields (Extension p k) (Extension p k) Source # | |
(*^) :: TowerOfFields k l => k -> l -> l infixl 7 Source #
Scalar multiplication.
Roots of unity
class Group g => CyclicSubgroup g where Source #
Cyclic subgroups of finite groups.
data RootsOfUnity (n :: Nat) k Source #
n
-th roots of unity of Galois fields.
Instances
cardinality :: forall n k. (KnownNat n, GaloisField k) => RootsOfUnity n k -> Natural Source #
Cardinality of subgroup.
cofactor :: forall n k. (KnownNat n, GaloisField k) => RootsOfUnity n k -> Natural Source #
Cofactor of subgroup in group.
isPrimitiveRootOfUnity :: (KnownNat n, GaloisField k) => RootsOfUnity n k -> Bool Source #
Check if element is primitive root of unity.
isRootOfUnity :: (KnownNat n, GaloisField k) => RootsOfUnity n k -> Bool Source #
Check if element is root of unity.
toU :: forall n k. (KnownNat n, GaloisField k) => k -> RootsOfUnity n k Source #
Safe convert from field to roots of unity.
toU' :: forall n k. (KnownNat n, GaloisField k) => k -> RootsOfUnity n k Source #
Unsafe convert from field to roots of unity.