ac-library-hs-1.4.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.Extra.Math.Montgomery64

Description

Fast modular multiplication for Word64 using Montgomery multiplication.

  • The modulus value must be odd.
  • If the modulus value is known to fit in 32 bits, AtCoder.Internal.Barrett can be faster.

Since: 1.2.6.0

Synopsis

Montgomery64

data Montgomery64 Source #

Fast modular multiplication for Word64 using Montgomery64 multiplication.

Since: 1.2.6.0

Instances

Instances details
Show Montgomery64 Source #

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.Math.Montgomery64

Methods

showsPrec :: Int -> Montgomery64 -> ShowS #

show :: Montgomery64 -> String #

showList :: [Montgomery64] -> ShowS #

Eq Montgomery64 Source #

NOTE: The represented value can be equal even if the internal values are different, so use eq for comparison.

Since: 1.2.6.0

Instance details

Defined in AtCoder.Extra.Math.Montgomery64

Methods

(==) :: Montgomery64 -> Montgomery64 -> Bool #

(/=) :: Montgomery64 -> Montgomery64 -> Bool #

Constructor

new :: forall (a :: Nat). (HasCallStack, KnownNat a) => Proxy# a -> Montgomery64 Source #

\(O(1)\) Static, shared storage of Montgomery64.

Constraints

  • \(m \le 2^{62}\)
  • \(m\) is odd

Since: 1.2.6.0

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

eq :: Word64 -> Word64 -> Word64 -> Bool Source #

\(O(1)\) Compares two values of Montgomery form and returns whether they represent the same value.

Since: 1.2.6.0