HMath.Algebra¶

Description

Algebraic interfaces, exact law checks, checked modular rings, and finite extension fields GF(p^n). Runtime moduli are deliberately not Num instances: combining different rings is an explicit error. Finite fields are constructed only after primality and irreducibility have been proved under a budget.

On this page¶

API	Purpose
Semiring	Commutative addition, associative multiplication, distributivity, additive identity and absorbing zero.
zero	Additive identity.
one	Additive identity.
plus	Additive identity.
times	Additive identity.
Ring	A semiring whose additive monoid is an abelian group.
negateRing	Additive inverse.
Field	A commutative ring in which each nonzero element has an inverse.
inverseField	Multiplicative inverse; zero returns a domain error.
Group	An associative operation with identity and inverse.
groupIdentity	Group identity.
groupCombine	Group identity.
groupInverse	Group identity.
Additive	A ring viewed as its additive group.
Additive	Declaration and type contract below.
getAdditive	Recover the underlying ring element.
Module	A left module with checked addition for runtime vector shapes.
moduleScale	Scalar action.
moduleAdd	Scalar action.
VectorSpace	A module over a field.
linearCombination	Checked linear combination.
semiringLaws	Exhaustive semiring identities on the supplied finite sample.
ringLaws	Semiring laws plus additive inverses on a finite sample.
fieldLaws	Ring laws, commutative multiplication and nonzero inverses.
groupLaws	Group identities on a finite sample.
moduleLaws	Check module scalar identity, composition, and both distributive laws.
Modular	A canonical residue in Z/mZ, retaining its runtime modulus.
modular	Construct a residue, requiring m>1; arbitrary signed values are reduced.
modularValue	Canonical value in [0,m).
modularModulus	Modulus greater than one.
addModular	Checked residue addition.
subtractModular	Checked residue subtraction.
multiplyModular	Checked residue multiplication.
inverseModular	Invert a unit; zero and nonunits are domain errors.
powerModular	Integer power, with negative powers supported for units.
FiniteField	An irreducible monic modulus over the proven prime field F_p.
finiteField	Construct GF(p^n) from an irreducible polynomial of positive degree.
primeField	Prime field GF(p), represented as F_p[x]/(x).
fieldCharacteristic	Prime characteristic p.
fieldDegree	Extension degree n.
fieldCardinality	Exact carrier size p^n.
fieldModulus	Ascending coefficients of the monic irreducible defining polynomial.
FieldElement	A canonical residue polynomial of degree smaller than its field degree.
fieldElement	Reduce an arbitrary integer polynomial into a finite field.
fieldElementCoefficients	Canonical ascending residue coefficients (trailing zeros removed).
fieldElements	Enumerate the complete carrier, rejecting sizes above an explicit storage budget.
addField	Addition; different defining fields are rejected even if isomorphic.
negateField	Additive inverse in the same field.
subtractField	Checked field subtraction.
multiplyField	Checked field multiplication, reduced modulo the defining polynomial.
inverseFieldElement	Nonzero inverse via the finite-field identity a^(q-2).
powerField	Binary exponentiation, with inverses for negative exponents.
finiteFieldLaws	Exhaustive carrier checks for small fields, including distributivity, associativity, identities and every nonzero inverse.

Documentation

Semiring

class Semiring a where Source #

Commutative addition, associative multiplication, distributivity, additive identity and absorbing zero. Multiplication need not be commutative.

Methods

zero :: a Source #

Additive identity.

one :: a Source #

Multiplicative identity.

plus :: a -> a -> a Source #

Semiring addition.

times :: a -> a -> a Source #

Semiring multiplication.

Instances

Instances details

Semiring Rational Source #
Instance details Defined in HMath.Algebra Methods zero :: Rational Source # one :: Rational Source # plus :: Rational -> Rational -> Rational Source # times :: Rational -> Rational -> Rational Source #
Semiring Integer Source #
Instance details Defined in HMath.Algebra Methods zero :: Integer Source # one :: Integer Source # plus :: Integer -> Integer -> Integer Source # times :: Integer -> Integer -> Integer Source #
(Eq a, Num a) => Semiring (Polynomial a) Source #
Instance details Defined in HMath.Algebra Methods zero :: Polynomial a Source # one :: Polynomial a Source # plus :: Polynomial a -> Polynomial a -> Polynomial a Source # times :: Polynomial a -> Polynomial a -> Polynomial a Source #

Ring

class Semiring a => Ring a where Source #

A semiring whose additive monoid is an abelian group.

Methods

negateRing :: a -> a Source #

Additive inverse.

Instances

Instances details

Ring Rational Source #
Instance details Defined in HMath.Algebra Methods negateRing :: Rational -> Rational Source #
Ring Integer Source #
Instance details Defined in HMath.Algebra Methods negateRing :: Integer -> Integer Source #
(Eq a, Num a) => Ring (Polynomial a) Source #
Instance details Defined in HMath.Algebra Methods negateRing :: Polynomial a -> Polynomial a Source #

Field

class Ring a => Field a where Source #

A commutative ring in which each nonzero element has an inverse.

Methods

inverseField :: a -> Either MathError a Source #

Multiplicative inverse; zero returns a domain error.

Instances

Instances details

Field Rational Source #
Instance details Defined in HMath.Algebra Methods inverseField :: Rational -> Either MathError Rational Source #

Group

class Group a where Source #

An associative operation with identity and inverse.

Methods

groupIdentity :: a Source #

Group identity.

groupCombine :: a -> a -> a Source #

Group operation, not necessarily commutative.

groupInverse :: a -> a Source #

Two-sided inverse.

Instances

Instances details

Ring a => Group (Additive a) Source #
Instance details Defined in HMath.Algebra Methods groupIdentity :: Additive a Source # groupCombine :: Additive a -> Additive a -> Additive a Source # groupInverse :: Additive a -> Additive a Source #

Additive

newtype Additive a Source #

A ring viewed as its additive group.

Constructors

Additive
Fields getAdditive :: a Recover the underlying ring element.

Instances

Instances details

Show a => Show (Additive a) Source #
Instance details Defined in HMath.Algebra Methods showsPrec :: Int -> Additive a -> ShowS # show :: Additive a -> String # showList :: [Additive a] -> ShowS #
Eq a => Eq (Additive a) Source #
Instance details Defined in HMath.Algebra Methods (==) :: Additive a -> Additive a -> Bool # (/=) :: Additive a -> Additive a -> Bool #
Ring a => Group (Additive a) Source #
Instance details Defined in HMath.Algebra Methods groupIdentity :: Additive a Source # groupCombine :: Additive a -> Additive a -> Additive a Source # groupInverse :: Additive a -> Additive a Source #

Module

class Ring scalar => Module scalar vector | vector -> scalar where Source #

A left module with checked addition for runtime vector shapes.

Methods

moduleScale :: scalar -> vector -> vector Source #

Scalar action.

moduleAdd :: vector -> vector -> Either MathError vector Source #

Addition, rejecting incompatible runtime shapes.

Instances

Instances details

Module Rational [Rational] Source #
Instance details Defined in HMath.Algebra Methods moduleScale :: Rational -> [Rational] -> [Rational] Source # moduleAdd :: [Rational] -> [Rational] -> Either MathError [Rational] Source #
Module Integer [Integer] Source #
Instance details Defined in HMath.Algebra Methods moduleScale :: Integer -> [Integer] -> [Integer] Source # moduleAdd :: [Integer] -> [Integer] -> Either MathError [Integer] Source #

VectorSpace

class (Field scalar, Module scalar vector) => VectorSpace scalar vector Source #

A module over a field. Rational finite-list vectors are an exact instance; list lengths define separate spaces, and moduleAdd rejects differing lengths.

Instances

Instances details

VectorSpace Rational [Rational] Source #
Instance details Defined in HMath.Algebra

linearCombination

linearCombination :: Module s v => v -> [(s, v)] -> Either MathError v Source #

Checked linear combination. Supply the zero vector explicitly so the empty combination retains its dimension.

semiringLaws

semiringLaws :: (Eq a, Semiring a) => [a] -> [(String, Bool)] Source #

Exhaustive semiring identities on the supplied finite sample. This is a test utility, not a proof for types with an infinite carrier.

ringLaws

ringLaws :: (Eq a, Ring a) => [a] -> [(String, Bool)] Source #

Semiring laws plus additive inverses on a finite sample.

fieldLaws

fieldLaws :: (Eq a, Field a) => [a] -> [(String, Bool)] Source #

Ring laws, commutative multiplication and nonzero inverses.

groupLaws

groupLaws :: (Eq a, Group a) => [a] -> [(String, Bool)] Source #

Group identities on a finite sample.

moduleLaws

moduleLaws :: (Eq v, Module s v) => [s] -> [v] -> [(String, Bool)] Source #

Check module scalar identity, composition, and both distributive laws. Vectors in the sample must belong to the same runtime space.

Modular

data Modular Source #

A canonical residue in Z/mZ, retaining its runtime modulus.

Instances

Instances details

Show Modular Source #
Instance details Defined in HMath.Algebra Methods showsPrec :: Int -> Modular -> ShowS # show :: Modular -> String # showList :: [Modular] -> ShowS #
Eq Modular Source #
Instance details Defined in HMath.Algebra Methods (==) :: Modular -> Modular -> Bool # (/=) :: Modular -> Modular -> Bool #

modular

modular :: Integer -> Integer -> Either MathError Modular Source #

Construct a residue, requiring m>1; arbitrary signed values are reduced.

modularValue

modularValue :: Modular -> Integer Source #

Canonical value in [0,m).

modularModulus

modularModulus :: Modular -> Integer Source #

Modulus greater than one.

addModular

addModular :: Modular -> Modular -> Either MathError Modular Source #

Checked residue addition.

subtractModular

subtractModular :: Modular -> Modular -> Either MathError Modular Source #

Checked residue subtraction.

multiplyModular

multiplyModular :: Modular -> Modular -> Either MathError Modular Source #

Checked residue multiplication.

inverseModular

inverseModular :: Modular -> Either MathError Modular Source #

Invert a unit; zero and nonunits are domain errors.

powerModular

powerModular :: Modular -> Integer -> Either MathError Modular Source #

Integer power, with negative powers supported for units.

FiniteField

data FiniteField Source #

An irreducible monic modulus over the proven prime field F_p. Coefficients are ascending canonical residues.

Instances

Instances details

Show FiniteField Source #
Instance details Defined in HMath.Algebra Methods showsPrec :: Int -> FiniteField -> ShowS # show :: FiniteField -> String # showList :: [FiniteField] -> ShowS #
Eq FiniteField Source #
Instance details Defined in HMath.Algebra Methods (==) :: FiniteField -> FiniteField -> Bool # (/=) :: FiniteField -> FiniteField -> Bool #

finiteField

finiteField :: Int -> Integer -> [Integer] -> Either MathError FiniteField Source #

Construct GF(p^n) from an irreducible polynomial of positive degree. Primality is proven by trial division. Irreducibility uses successive Frobenius powers and polynomial gcds; n must not exceed the proof budget.

primeField

primeField :: Int -> Integer -> Either MathError FiniteField Source #

Prime field GF(p), represented as F_p[x]/(x).

fieldCharacteristic

fieldCharacteristic :: FiniteField -> Integer Source #

Prime characteristic p.

fieldDegree

fieldDegree :: FiniteField -> Int Source #

Extension degree n.

fieldCardinality

fieldCardinality :: FiniteField -> Integer Source #

Exact carrier size p^n.

fieldModulus

fieldModulus :: FiniteField -> [Integer] Source #

Ascending coefficients of the monic irreducible defining polynomial.

FieldElement

data FieldElement Source #

A canonical residue polynomial of degree smaller than its field degree.

Instances

Instances details

Show FieldElement Source #
Instance details Defined in HMath.Algebra Methods showsPrec :: Int -> FieldElement -> ShowS # show :: FieldElement -> String # showList :: [FieldElement] -> ShowS #
Eq FieldElement Source #
Instance details Defined in HMath.Algebra Methods (==) :: FieldElement -> FieldElement -> Bool # (/=) :: FieldElement -> FieldElement -> Bool #

fieldElement

fieldElement :: FiniteField -> [Integer] -> FieldElement Source #

Reduce an arbitrary integer polynomial into a finite field.

fieldElementCoefficients

fieldElementCoefficients :: FieldElement -> [Integer] Source #

Canonical ascending residue coefficients (trailing zeros removed).

fieldElements

fieldElements :: Int -> FiniteField -> Either MathError [FieldElement] Source #

Enumerate the complete carrier, rejecting sizes above an explicit storage budget. Enumeration is coefficient-lexicographic and deterministic.

addField

addField :: FieldElement -> FieldElement -> Either MathError FieldElement Source #

Addition; different defining fields are rejected even if isomorphic.

negateField

negateField :: FieldElement -> FieldElement Source #

Additive inverse in the same field.

subtractField

subtractField :: FieldElement -> FieldElement -> Either MathError FieldElement Source #

Checked field subtraction.

multiplyField

multiplyField :: FieldElement -> FieldElement -> Either MathError FieldElement Source #

Checked field multiplication, reduced modulo the defining polynomial.

inverseFieldElement

inverseFieldElement :: FieldElement -> Either MathError FieldElement Source #

Nonzero inverse via the finite-field identity a^(q-2).

powerField

powerField :: FieldElement -> Integer -> Either MathError FieldElement Source #

Binary exponentiation, with inverses for negative exponents.

finiteFieldLaws

finiteFieldLaws :: Int -> FiniteField -> Either MathError [(String, Bool)] Source #

Exhaustive carrier checks for small fields, including distributivity, associativity, identities and every nonzero inverse. Budget bounds enumeration; the cubic law checks are intended for small validation fields.