finite-fields-0.2: Arithmetic in finite fields
Safe HaskellNone
LanguageHaskell2010

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 

Instances

Instances details
Show (WitnessFp p) Source # 
Instance details

Defined in Math.FiniteField.PrimeField.Small

data SomeWitnessFp Source #

Constructors

forall p. SomeWitnessFp (WitnessFp p) 

Instances

Instances details
Show SomeWitnessFp Source # 
Instance details

Defined in Math.FiniteField.PrimeField.Small

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