Newtype wrapper that represents \( \mathbb{Z}/p\mathbb{Z} \) for prime p. ModP is a Field i.e. supports addition, subtraction, multiplication, and division.

When constructing a ModP p a we must verify that p is prime and the type a is large enough to accommodate p, hence the possible failure.

Examples

>>> import Data.Text.Display (display)
>>> display $ unsafeModP @7 10
"3 (mod 7)"

Since: 0.1

Constructor for ModP. Fails if p is not prime. This uses the Miller-Rabin primality test, which has complexity \(O(k \log^3 p)\), and we take \(k = 100\). See wikipedia for more details.

Examples

>>> mkModP @5 7
Right (MkModP 2 (mod 5))

>>> mkModP @10 7
Left "Received non-prime: 10"

>>> mkModP @128 (9 :: Int8)
Left "Type 'Int8' has a maximum size of 127. This is not large enough to safely implement mod 128."

Since: 0.1

Template haskell for creating a ModP at compile-time.

Examples

>>> $$(mkModPTH @11 7)
MkModP 7 (mod 11)

Since: 0.1

Variant of mkModP that throws an error when given a non-prime.

WARNING: Partial

Examples

>>> unsafeModP @7 12
MkModP 5 (mod 7)

Since: 0.1

This function reduces the argument modulo p but does not check that p is prime. Note that the correct behavior of some functionality (e.g. division) is reliant on primality, so this is dangerous. This is intended only for when we absolutely know p is prime and the check is undesirable for performance reasons. Exercise extreme caution.

Since: 0.1

Since: 0.1

Given non-zero \(d\), returns the inverse i.e. finds \(e\) s.t.

\[ de \equiv 1 \pmod p. \]

Examples

>>> invert $ unsafeModP @19 12
MkModP 8 (mod 19)

Since: 0.1

ReversedPrism' that enables total elimination and partial construction.

Examples

>>> import Optics.Core (view)
>>> n = $$(mkModPTH @7 9)
>>> view _MkModP n
2

>>> rmatching (_MkModP @7) 9
Right (MkModP 2 (mod 7))

>>> rmatching (_MkModP @6) 9
Left 9

Since: 0.1

Reversed matching. Useful with smart-constructor optics.

Since: 0.1