finite-fields-0.2.0.1: Arithmetic in finite fields

Math.FiniteField.PrimeField.Small

Description

Small prime fields, up to p < 2^31 (using Word64 under the hood).

This should be faster than the generic implementation which uses Integer under the hood.

NB: Because the multiplication of two 32 bit integers needs 64 bits, the limit is 2^32 and not 2^64. And because I'm lazy right now to check if everything works properly unsigned, the actual limit is 2^31 instead :)

Synopsis

# Witness for the existence of the field

newtype WitnessFp (p :: Nat) Source #

A witness for the existence of the prime field F_p

Constructors

 WitnessFp FieldsfromWitnessFp :: IsSmallPrime p

#### Instances

Instances details
 Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small MethodsshowsPrec :: Int -> WitnessFp p -> ShowS #show :: WitnessFp p -> String #showList :: [WitnessFp p] -> ShowS #

Constructors

 forall p. SomeWitnessFp (WitnessFp p)

#### Instances

Instances details
 Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small MethodsshowList :: [SomeWitnessFp] -> ShowS #

Note: currently this checks the primality of the input using trial division, so it's only practical for (very) small primes...

But you can use unsafeSmallPrimeField to cheat.

You are responsible for guaranteeing that the input is a prime.

# Field elements

data Fp (p :: Nat) Source #

An element of the prime field F_p

#### Instances

Instances details
 Num (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small Methods(+) :: Fp p -> Fp p -> Fp p #(-) :: Fp p -> Fp p -> Fp p #(*) :: Fp p -> Fp p -> Fp p #negate :: Fp p -> Fp p #abs :: Fp p -> Fp p #signum :: Fp p -> Fp p # Fractional (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small Methods(/) :: Fp p -> Fp p -> Fp p #recip :: Fp p -> Fp p # Show (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small MethodsshowsPrec :: Int -> Fp p -> ShowS #show :: Fp p -> String #showList :: [Fp p] -> ShowS # Field (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small Associated Typestype Witness (Fp p) = (w :: Type) Source #type Prime (Fp p) :: Nat Source #type Dim (Fp p) :: Nat Source # Methodsdimension :: Witness (Fp p) -> Integer Source #fieldSize :: Witness (Fp p) -> Integer Source #zero :: Witness (Fp p) -> Fp p Source #one :: Witness (Fp p) -> Fp p Source #isZero :: Fp p -> Bool Source #isOne :: Fp p -> Bool Source #embed :: Witness (Fp p) -> Integer -> Fp p Source #embedSmall :: Witness (Fp p) -> Int -> Fp p Source #randomFieldElem :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen) Source #randomInvertible :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen) Source #primGen :: Witness (Fp p) -> Fp p Source #witnessOf :: Fp p -> Witness (Fp p) Source #power :: Fp p -> Integer -> Fp p Source #powerSmall :: Fp p -> Int -> Fp p Source #frobenius :: Fp p -> Fp p Source #enumerate :: Witness (Fp p) -> [Fp p] Source # Eq (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small Methods(==) :: Fp p -> Fp p -> Bool #(/=) :: Fp p -> Fp p -> Bool # Ord (Fp p) Source # Note: the Ord instance is present only so that you can use GF as key in Maps - the ordering is kind of arbitrary! Instance detailsDefined in Math.FiniteField.PrimeField.Small Methodscompare :: Fp p -> Fp p -> Ordering #(<) :: Fp p -> Fp p -> Bool #(<=) :: Fp p -> Fp p -> Bool #(>) :: Fp p -> Fp p -> Bool #(>=) :: Fp p -> Fp p -> Bool #max :: Fp p -> Fp p -> Fp p #min :: Fp p -> Fp p -> Fp p # type Dim (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small type Dim (Fp p) = 1 type Prime (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small type Prime (Fp p) = p type Witness (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small type Witness (Fp p) = WitnessFp p