| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.Math.Montgomery64
Description
Fast modular multiplication for Word64 using Montgomery multiplication. If the modulus value
is known to fit in 32 bits, use the AtCoder.Internal.Barrett module instead.
Since: 1.2.6.0
Synopsis
- data Montgomery64
- new :: forall (a :: Nat). (HasCallStack, KnownNat a) => Proxy# a -> Montgomery64
- fromVal :: HasCallStack => Word64 -> Montgomery64
- umod :: Montgomery64 -> Word64
- encode :: Montgomery64 -> Word64 -> Word64
- decode :: Montgomery64 -> Word64 -> Word64
- reduce :: Montgomery64 -> Word128 -> Word64
- addMod :: Word64 -> Word64 -> Word64 -> Word64
- subMod :: Word64 -> Word64 -> Word64 -> Word64
- mulMod :: Montgomery64 -> Word64 -> Word64 -> Word64
- powMod :: HasCallStack => Montgomery64 -> Word64 -> Int -> Word64
- eq :: Word64 -> Word64 -> Word64 -> Bool
Montgomery64
data Montgomery64 Source #
Fast modular multiplication for Word64 using Montgomery64 multiplication.
Since: 1.2.6.0
Instances
| Show Montgomery64 Source # | Since: 1.2.6.0 |
Defined in AtCoder.Extra.Math.Montgomery64 Methods showsPrec :: Int -> Montgomery64 -> ShowS # show :: Montgomery64 -> String # showList :: [Montgomery64] -> ShowS # | |
| Eq Montgomery64 Source # | Since: 1.2.6.0 |
Defined in AtCoder.Extra.Math.Montgomery64 | |
Constructor
new :: forall (a :: Nat). (HasCallStack, KnownNat a) => Proxy# a -> Montgomery64 Source #
fromVal :: HasCallStack => Word64 -> Montgomery64 Source #
\(O(1)\) Creates a Montgomery64 for a modulus value \(m\) of type Word64 value.
Constraints
- (m le 2^{62})
- \(m\) is odd
Since: 1.2.6.0
Accessor
umod :: Montgomery64 -> Word64 Source #
\(O(1)\) Retrieves the modulus \(m\).
Since: 1.2.6.0
Montgomery form encoding
encode :: Montgomery64 -> Word64 -> Word64 Source #
\(O(1)\) Converts the given Word64 to Montgomery form.
Since: 1.2.6.0
decode :: Montgomery64 -> Word64 -> Word64 Source #
\(O(1)\) Retrieves the value from a Montgomery form of value.
Since: 1.2.6.0
reduce :: Montgomery64 -> Word128 -> Word64 Source #
\(O(1)\) Takes the mod in Montgomery form.
Since: 1.2.6.0
Calculations
addMod :: Word64 -> Word64 -> Word64 -> Word64 Source #
\(O(1)\) Calculates \(a + b \bmod m\) in the Montgomery form.
subMod :: Word64 -> Word64 -> Word64 -> Word64 Source #
\(O(1)\) Calculates \(a - b \bmod m\) in the Montgomery form.
mulMod :: Montgomery64 -> Word64 -> Word64 -> Word64 Source #
\(O(1)\) Calculates \(a^n \bmod m\) in the Montgomery form.
Since: 1.2.6.0
powMod :: HasCallStack => Montgomery64 -> Word64 -> Int -> Word64 Source #
\(O(w)\) Calculates \(a^n \bmod m\) in the Montgomery form.
Since: 1.2.6.0