Safe Haskell | None |
---|---|
Language | Haskell2010 |
Internal module for ModP
.
Since: 0.1
Synopsis
- newtype ModP (p :: Nat) a where
- UnsafeModP a
- pattern MkModP :: a -> ModP p a
- mkModP :: forall (p :: Nat) a. (Integral a, KnownNat p, MaybeUpperBounded a, Typeable a) => a -> Either String (ModP p a)
- unsafeModP :: forall (p :: Nat) a. (HasCallStack, Integral a, KnownNat p, MaybeUpperBounded a, Typeable a) => a -> ModP p a
- invert :: forall (p :: Nat) a. (Integral a, KnownNat p) => ModP p a -> ModP p a
- reallyUnsafeModP :: forall (p :: Nat) a. (Integral a, KnownNat p) => a -> ModP p a
- errMsg :: String -> String -> String
Type
newtype ModP (p :: Nat) a Source #
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
we must verify that ModP
p ap
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
pattern MkModP :: a -> ModP p a | Unidirectional pattern synonym for Since: 0.1 |
Instances
Functions
mkModP :: forall (p :: Nat) a. (Integral a, KnownNat p, MaybeUpperBounded a, Typeable a) => a -> Either String (ModP p a) Source #
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
unsafeModP :: forall (p :: Nat) a. (HasCallStack, Integral a, KnownNat p, MaybeUpperBounded a, Typeable a) => a -> ModP p a Source #
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
invert :: forall (p :: Nat) a. (Integral a, KnownNat p) => ModP p a -> ModP p a Source #
Given non-zero \(d\), returns the inverse i.e. finds \(e\) s.t.
\[ de \equiv 1 \pmod p. \]
Examples
findInverse >>> invert $ unsafeModP @7 5 MkModP 3 (mod 7)
>>>
invert $ unsafeModP @19 12
MkModP 8 (mod 19)
Since: 0.1
reallyUnsafeModP :: forall (p :: Nat) a. (Integral a, KnownNat p) => a -> ModP p a Source #
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