Math.FiniteField.PrimeField.Small

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 :)

Witness for the existence of the field

newtype WitnessFp (p :: Nat)

A witness for the existence of the prime field F_p

Constructors

WitnessFp

Fields

• fromWitnessFp :: IsSmallPrime p

Instances

Show (WitnessFp p)

Defined in Math.FiniteField.PrimeField.Small

Methods

showsPrec :: Int -> WitnessFp p -> ShowS

show :: WitnessFp p -> String

showList :: [WitnessFp p] -> ShowS

data SomeWitnessFp

Constructors

forall p. SomeWitnessFp (WitnessFp p)

Instances

Show SomeWitnessFp

Defined in Math.FiniteField.PrimeField.Small

Methods

showsPrec :: Int -> SomeWitnessFp -> ShowS

show :: SomeWitnessFp -> String

showList :: [SomeWitnessFp] -> ShowS

mkSmallPrimeField :: Int -> Maybe SomeWitnessFp

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.

unsafeSmallPrimeField :: Int -> SomeWitnessFp

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

Field elements

data Fp (p :: Nat)

An element of the prime field F_p

Instances

Num (Fp p)

Defined 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

fromInteger :: Integer -> Fp p

Fractional (Fp p)

Defined in Math.FiniteField.PrimeField.Small

Methods

(/) :: Fp p -> Fp p -> Fp p

recip :: Fp p -> Fp p

fromRational :: Rational -> Fp p

Show (Fp p)

Defined in Math.FiniteField.PrimeField.Small

Methods

showsPrec :: Int -> Fp p -> ShowS

show :: Fp p -> String

showList :: [Fp p] -> ShowS

Field (Fp p)

Defined in Math.FiniteField.PrimeField.Small

Associated Types

type Witness (Fp p) = (w :: Type)

type Prime (Fp p) :: Nat

type Dim (Fp p) :: Nat

Methods

characteristic :: Witness (Fp p) -> Integer

dimension :: Witness (Fp p) -> Integer

fieldSize :: Witness (Fp p) -> Integer

zero :: Witness (Fp p) -> Fp p

one :: Witness (Fp p) -> Fp p

isZero :: Fp p -> Bool

isOne :: Fp p -> Bool

embed :: Witness (Fp p) -> Integer -> Fp p

embedSmall :: Witness (Fp p) -> Int -> Fp p

randomFieldElem :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen)

randomInvertible :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen)

primGen :: Witness (Fp p) -> Fp p

witnessOf :: Fp p -> Witness (Fp p)

power :: Fp p -> Integer -> Fp p

powerSmall :: Fp p -> Int -> Fp p

frobenius :: Fp p -> Fp p

enumerate :: Witness (Fp p) -> [Fp p]

Eq (Fp p)

Defined in Math.FiniteField.PrimeField.Small

Methods

(==) :: Fp p -> Fp p -> Bool

(/=) :: Fp p -> Fp p -> Bool

Ord (Fp p)

Note: the Ord instance is present only so that you can use GF as key in Maps - the ordering is kind of arbitrary!

Defined in Math.FiniteField.PrimeField.Small

Methods

compare :: 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)

Defined in Math.FiniteField.PrimeField.Small

type Dim (Fp p) = 1

type Prime (Fp p)

Defined in Math.FiniteField.PrimeField.Small

type Prime (Fp p) = p

type Witness (Fp p)

Defined in Math.FiniteField.PrimeField.Small

type Witness (Fp p) = WitnessFp p

primRoot :: IsSmallPrime p -> Fp p