Safe Haskell	None
Language	Haskell2010

Math.FiniteField.PrimeField.Small

Contents

Witness for the existence of the field
Field elements

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

newtype WitnessFp (p :: Nat) = WitnessFp {
- fromWitnessFp :: IsSmallPrime p
}
data SomeWitnessFp = forall p. SomeWitnessFp (WitnessFp p)
mkSmallPrimeField :: Int -> Maybe SomeWitnessFp
unsafeSmallPrimeField :: Int -> SomeWitnessFp
data Fp (p :: Nat)
primRoot :: IsSmallPrime p -> Fp p

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
Fields fromWitnessFp :: IsSmallPrime p

Instances

Instances details

Show (WitnessFp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small Methods showsPrec :: Int -> WitnessFp p -> ShowS # show :: WitnessFp p -> String # showList :: [WitnessFp p] -> ShowS #

data SomeWitnessFp Source #

Constructors

forall p. SomeWitnessFp (WitnessFp p)

Instances

Instances details

Show SomeWitnessFp Source #
Instance details Defined in Math.FiniteField.PrimeField.Small Methods showsPrec :: Int -> SomeWitnessFp -> ShowS # show :: SomeWitnessFp -> String # showList :: [SomeWitnessFp] -> ShowS #

mkSmallPrimeField :: Int -> Maybe SomeWitnessFp Source #

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 Source #

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

Eq (Fp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small Methods (==) :: Fp p -> Fp p -> Bool # (/=) :: Fp p -> Fp p -> Bool #
Fractional (Fp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small Methods (/) :: Fp p -> Fp p -> Fp p # recip :: Fp p -> Fp p # fromRational :: Rational -> Fp p #
Num (Fp p) Source #
Instance details 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 #
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 details 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 #
Show (Fp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small Methods showsPrec :: Int -> Fp p -> ShowS # show :: Fp p -> String # showList :: [Fp p] -> ShowS #
Field (Fp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small Associated Types type Witness (Fp p) = (w :: Type) Source # type Prime (Fp p) :: Nat Source # type Dim (Fp p) :: Nat Source # Methods characteristic :: Witness (Fp p) -> Integer Source # dimension :: 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 #
type Witness (Fp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small type Witness (Fp p) = WitnessFp p
type Prime (Fp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small type Prime (Fp p) = p
type Dim (Fp p) Source #
Instance details Defined in Math.FiniteField.PrimeField.Small type Dim (Fp p) = 1

primRoot :: IsSmallPrime p -> Fp p Source #