Module

# Data.ModularArithmetic

Package
purescript-modular-arithmetic
Repository
hdgarrood/purescript-modular-arithmetic

### #ZSource

``newtype Z m``

Integers modulo some positive integer m.

The type argument should be a positive integer of the kind defined by purescript-typelevel. This way, the modulus that you're working with is specified in the type. Note that even though the modulus is captured at the type level, you can still use modulus values which are not known at compile time, with the `reifyIntP` function.

This type forms a commutative ring for any positive integer m, and additionally a field when m is prime. Unlike `Int` and `Number`, though, all of these instances are fully law-abiding.

The runtime representation is identical to that of `Int`, except that values are guaranteed to be between 0 and m-1.

#### Instances

• `Eq (Z m)`
• `Ord (Z m)`
• `Show (Z m)`
• `(Pos m) => Bounded (Z m)`
• `(Pos m) => Enum (Z m)`
• `(Pos m) => BoundedEnum (Z m)`
• `(Pos m) => Semiring (Z m)`
• `(Pos m) => Ring (Z m)`
• `(Pos m) => CommutativeRing (Z m)`
• `(Prime m) => DivisionRing (Z m)`
• `(Prime m) => EuclideanRing (Z m)`

### #mkZSource

``mkZ :: forall m. Pos m => Int -> Z m``

Smart constructor for `Z` values.

### #runZSource

``runZ :: forall m. Z m -> Int``

Get at the underlying `Int`.

### #modulusSource

``modulus :: forall m. Pos m => Z m -> Int``

Convenience function for accessing `m` at the value level.

### #inverseSource

``inverse :: forall m. Pos m => Z m -> Maybe (Z m)``

Compute a multiplicative inverse of some nonzero number in Z_m. Note that an inverse exists if and only if the input and `m` are coprime. If this is not the case, this function returns `Nothing`.

### #enumerateSource

``enumerate :: forall m. Pos m => NonEmpty Array (Z m)``

List all members of Z_m.

### #genZSource

``genZ :: forall gen m. MonadGen gen => Pos m => gen (Z m)``

A random generator for elements of Z_m; selects any value of Z_m with each value being equally likely to be selected.

## Re-exports from Data.ModularArithmetic.Primality

### #PrimeSource

``class (Pos m) <= Prime m ``

This class specifies that a type-level integer is prime; that is, it has exactly 2 divisors: itself, and 1.

All primes up to 100 have instances. For larger primes, you will need to use the `reifyPrime` function.

#### Instances

• `Prime D2`
• `Prime D3`
• `Prime D5`
• `Prime D7`
• `Prime (NumCons D1 D1)`
• `Prime (NumCons D1 D3)`
• `Prime (NumCons D1 D7)`
• `Prime (NumCons D1 D9)`
• `Prime (NumCons D2 D3)`
• `Prime (NumCons D2 D9)`
• `Prime (NumCons D3 D1)`
• `Prime (NumCons D3 D7)`
• `Prime (NumCons D4 D1)`
• `Prime (NumCons D4 D3)`
• `Prime (NumCons D4 D7)`
• `Prime (NumCons D5 D3)`
• `Prime (NumCons D5 D9)`
• `Prime (NumCons D6 D1)`
• `Prime (NumCons D6 D7)`
• `Prime (NumCons D7 D1)`
• `Prime (NumCons D7 D3)`
• `Prime (NumCons D7 D9)`
• `Prime (NumCons D8 D3)`
• `Prime (NumCons D8 D9)`
• `Prime (NumCons D9 D7)`

### #reifyPrimeSource

``reifyPrime :: forall r. Int -> (forall p. Prime p => p -> r) -> Maybe r``

Reify a prime number at the type level. If the first argument provided is not prime, this function returns `Nothing`.

``primeFactors :: Int -> List Int``

Find prime factors by trial division; first attempting to divide by 2 and then by every odd number after that. This is the most basic prime factorisation algorithm possible but it is more than enough for this case (specifically, when the input is guaranteed to be no more than 2^31).

Prime factors are returned in increasing order. For example:

``````> primeFactors 12
(2 : 2 : 3 : Nil)
``````

Passing in any number less than 2 will return an empty list.

``````> primeFactors (-12)
Nil
``````

For all positive integers, the following properties are satisfied:

``````> product (primeFactors n) == n
> all isPrime (primeFactors n)
``````

### #isPrimeSource

``isPrime :: Int -> Boolean``

Check if a number is prime. Note that 1 is not a prime number.