arithmoi-0.10.0.0: Efficient basic number-theoretic functions.

Math.NumberTheory.Moduli.Singleton

Description

Singleton data types.

Synopsis

# SFactors singleton

data SFactors a (m :: Nat) Source #

This singleton data type establishes a correspondence between a modulo m on type level and its factorisation on term level.

Instances
 Ord a => Eq (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methods(==) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(/=) :: Some (SFactors a) -> Some (SFactors a) -> Bool # Ord a => Ord (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodscompare :: Some (SFactors a) -> Some (SFactors a) -> Ordering #(<) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(<=) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(>) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(>=) :: Some (SFactors a) -> Some (SFactors a) -> Bool #max :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) #min :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) # Show a => Show (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton MethodsshowsPrec :: Int -> Some (SFactors a) -> ShowS #show :: Some (SFactors a) -> String #showList :: [Some (SFactors a)] -> ShowS # NFData a => NFData (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodsrnf :: Some (SFactors a) -> () # Eq (SFactors a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methods(==) :: SFactors a m -> SFactors a m -> Bool #(/=) :: SFactors a m -> SFactors a m -> Bool # Ord (SFactors a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodscompare :: SFactors a m -> SFactors a m -> Ordering #(<) :: SFactors a m -> SFactors a m -> Bool #(<=) :: SFactors a m -> SFactors a m -> Bool #(>) :: SFactors a m -> SFactors a m -> Bool #(>=) :: SFactors a m -> SFactors a m -> Bool #max :: SFactors a m -> SFactors a m -> SFactors a m #min :: SFactors a m -> SFactors a m -> SFactors a m # Show a => Show (SFactors a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton MethodsshowsPrec :: Int -> SFactors a m -> ShowS #show :: SFactors a m -> String #showList :: [SFactors a m] -> ShowS # Generic (SFactors a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Associated Typestype Rep (SFactors a m) :: Type -> Type # Methodsfrom :: SFactors a m -> Rep (SFactors a m) x #to :: Rep (SFactors a m) x -> SFactors a m # NFData a => NFData (SFactors a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodsrnf :: SFactors a m -> () # type Rep (SFactors a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton type Rep (SFactors a m) = D1 (MetaData "SFactors" "Math.NumberTheory.Moduli.Singleton" "arithmoi-0.10.0.0-ERYv2VuF0BeGX7OVoZ5V00" True) (C1 (MetaCons "SFactors" PrefixI True) (S1 (MetaSel (Just "unSFactors") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [(Prime a, Word)])))

sfactors :: forall a m. (Ord a, UniqueFactorisation a, KnownNat m) => SFactors a m Source #

Create a singleton from a type-level positive modulo m, passed in a constraint.

>>> :set -XDataKinds
>>> sfactors :: SFactors Integer 13
SFactors {sfactorsFactors = [(Prime 13,1)]}


someSFactors :: (Ord a, Num a) => [(Prime a, Word)] -> Some (SFactors a) Source #

Create a singleton from factors of m. Factors must be distinct, as in output of factorise.

>>> import Math.NumberTheory.Primes
>>> someSFactors (factorise 98)
SFactors {sfactorsFactors = [(Prime 2,1),(Prime 7,2)]}


unSFactors :: SFactors a m -> [(Prime a, Word)] Source #

Factors of m.

proofFromSFactors :: Integral a => SFactors a m -> () :- KnownNat m Source #

Convert a singleton to a proof that m is known. Usage example:

toModulo :: SFactors Integer m -> Natural
toModulo t = case proofFromSFactors t of Sub Dict -> natVal t

# CyclicGroup singleton

data CyclicGroup a (m :: Nat) Source #

This singleton data type establishes a correspondence between a modulo m on type level and a cyclic group of the same order on term level.

Instances
 Eq a => Eq (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methods(==) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(/=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool # Ord a => Ord (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodscompare :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Ordering #(<) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(<=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(>) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(>=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #max :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) #min :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) # Show a => Show (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton MethodsshowsPrec :: Int -> Some (CyclicGroup a) -> ShowS #show :: Some (CyclicGroup a) -> String #showList :: [Some (CyclicGroup a)] -> ShowS # NFData a => NFData (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodsrnf :: Some (CyclicGroup a) -> () # Eq (CyclicGroup a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methods(==) :: CyclicGroup a m -> CyclicGroup a m -> Bool #(/=) :: CyclicGroup a m -> CyclicGroup a m -> Bool # Ord (CyclicGroup a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodscompare :: CyclicGroup a m -> CyclicGroup a m -> Ordering #(<) :: CyclicGroup a m -> CyclicGroup a m -> Bool #(<=) :: CyclicGroup a m -> CyclicGroup a m -> Bool #(>) :: CyclicGroup a m -> CyclicGroup a m -> Bool #(>=) :: CyclicGroup a m -> CyclicGroup a m -> Bool #max :: CyclicGroup a m -> CyclicGroup a m -> CyclicGroup a m #min :: CyclicGroup a m -> CyclicGroup a m -> CyclicGroup a m # Show a => Show (CyclicGroup a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton MethodsshowsPrec :: Int -> CyclicGroup a m -> ShowS #show :: CyclicGroup a m -> String #showList :: [CyclicGroup a m] -> ShowS # Generic (CyclicGroup a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Associated Typestype Rep (CyclicGroup a m) :: Type -> Type # Methodsfrom :: CyclicGroup a m -> Rep (CyclicGroup a m) x #to :: Rep (CyclicGroup a m) x -> CyclicGroup a m # NFData a => NFData (CyclicGroup a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodsrnf :: CyclicGroup a m -> () # type Rep (CyclicGroup a m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton type Rep (CyclicGroup a m) = D1 (MetaData "CyclicGroup" "Math.NumberTheory.Moduli.Singleton" "arithmoi-0.10.0.0-ERYv2VuF0BeGX7OVoZ5V00" False) ((C1 (MetaCons "CG2'" PrefixI False) (U1 :: Type -> Type) :+: C1 (MetaCons "CG4'" PrefixI False) (U1 :: Type -> Type)) :+: (C1 (MetaCons "CGOddPrimePower'" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Prime a)) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word)) :+: C1 (MetaCons "CGDoubleOddPrimePower'" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Prime a)) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word))))

cyclicGroup :: forall a m. (Integral a, UniqueFactorisation a, KnownNat m) => Maybe (CyclicGroup a m) Source #

Create a singleton from a type-level positive modulo m, passed in a constraint.

>>> :set -XDataKinds
>>> import Data.Maybe
>>> cyclicGroup :: CyclicGroup Integer 169
CGOddPrimePower' (Prime 13) 2

>>> sfactorsToCyclicGroup (fromModulo 4)
Just CG4'
>>> sfactorsToCyclicGroup (fromModulo (2 * 13 ^ 3))
Just (CGDoubleOddPrimePower' (Prime 13) 3)
>>> sfactorsToCyclicGroup (fromModulo (4 * 13))
Nothing


cyclicGroupFromModulo :: (Integral a, UniqueFactorisation a) => a -> Maybe (Some (CyclicGroup a)) Source #

Similar to cyclicGroupFromFactors . factorise, but much faster, because it but performes only one primality test instead of full factorisation.

proofFromCyclicGroup :: Integral a => CyclicGroup a m -> () :- KnownNat m Source #

Convert a cyclic group to a proof that m is known. Usage example:

toModulo :: CyclicGroup Integer m -> Natural
toModulo t = case proofFromCyclicGroup t of Sub Dict -> natVal t

pattern CG2 :: CyclicGroup a m Source #

Unidirectional pattern for residues modulo 2.

pattern CG4 :: CyclicGroup a m Source #

Unidirectional pattern for residues modulo 4.

pattern CGOddPrimePower :: Prime a -> Word -> CyclicGroup a m Source #

Unidirectional pattern for residues modulo p^k for odd prime p.

pattern CGDoubleOddPrimePower :: Prime a -> Word -> CyclicGroup a m Source #

Unidirectional pattern for residues modulo 2p^k for odd prime p.

# SFactors <=> CyclicGroup

cyclicGroupToSFactors :: Num a => CyclicGroup a m -> SFactors a m Source #

Invert sfactorsToCyclicGroup.

>>> import Data.Maybe
>>> cyclicGroupToSFactors (fromJust (sfactorsToCyclicGroup (fromModulo 4)))
SFactors {sfactorsModulo = 4, sfactorsFactors = [(Prime 2,2)]}


sfactorsToCyclicGroup :: (Eq a, Num a) => SFactors a m -> Maybe (CyclicGroup a m) Source #

Check whether a multiplicative group of residues, characterized by its modulo, is cyclic and, if yes, return its form.

>>> sfactorsToCyclicGroup (fromModulo 4)
Just CG4'
>>> sfactorsToCyclicGroup (fromModulo (2 * 13 ^ 3))
Just (CGDoubleOddPrimePower' (Prime 13) 3)
>>> sfactorsToCyclicGroup (fromModulo (4 * 13))
Nothing


# Some wrapper

data Some (a :: Nat -> *) where Source #

Wrapper to hide an unknown type-level natural.

Constructors

 Some :: a m -> Some a
Instances
 Eq a => Eq (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methods(==) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(/=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool # Ord a => Eq (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methods(==) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(/=) :: Some (SFactors a) -> Some (SFactors a) -> Bool # Ord a => Ord (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodscompare :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Ordering #(<) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(<=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(>) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #(>=) :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Bool #max :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) #min :: Some (CyclicGroup a) -> Some (CyclicGroup a) -> Some (CyclicGroup a) # Ord a => Ord (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodscompare :: Some (SFactors a) -> Some (SFactors a) -> Ordering #(<) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(<=) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(>) :: Some (SFactors a) -> Some (SFactors a) -> Bool #(>=) :: Some (SFactors a) -> Some (SFactors a) -> Bool #max :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) #min :: Some (SFactors a) -> Some (SFactors a) -> Some (SFactors a) # Show a => Show (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton MethodsshowsPrec :: Int -> Some (CyclicGroup a) -> ShowS #show :: Some (CyclicGroup a) -> String #showList :: [Some (CyclicGroup a)] -> ShowS # Show a => Show (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton MethodsshowsPrec :: Int -> Some (SFactors a) -> ShowS #show :: Some (SFactors a) -> String #showList :: [Some (SFactors a)] -> ShowS # NFData a => NFData (Some (CyclicGroup a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodsrnf :: Some (CyclicGroup a) -> () # NFData a => NFData (Some (SFactors a)) Source # Instance detailsDefined in Math.NumberTheory.Moduli.Singleton Methodsrnf :: Some (SFactors a) -> () #