Montgomery Multiplication

Intuition, Vocabulary and Foundations

Ordinary modular multiplication computes $ab\bmod n$, and the remainder may require costly division. Montgomery multiplication changes representation so repeated reduction uses multiplication, addition, masking, and shifting. Choose $R=2^w>n$ with $\gcd(R,n)=1$ and encode $x$ as $\bar x=xR\bmod n$.

Multiplying encodings produces $xyR^2$; Montgomery reduction, or REDC, removes one factor of $R$ and returns $xyR\bmod n$, still encoded. For $n=17$ and $R=32$, the encodings of $5$ and $7$ are $7$ and $3$; their Montgomery product is $15$, the encoding of $1$.

Montgomery arithmetic replaces division by changing representation, then choosing a multiple of $n$ that cancels the low radix word exactly. A power-of-two radix requires an odd modulus because $n$ must be invertible modulo $R$.

Concept	Example	Boundary	Question answered
Montgomery form	For $n=17,R=32$, encode $5$ as $7$	Ordinary $5$ is not encoded $5$	What domain avoids repeated division?
Radix	$R=32>17$	$R=16$ is too small for the standard bound	Which power of two enables masks and shifts?
Coprimality	$\gcd(17,32)=1$	An even modulus shares a factor with $R$	Does the required inverse exist?
Negative inverse	$n'=-n^{-1}\bmod R$	Omitting the minus sign fails to cancel low bits	Which constant drives REDC?
REDC	$\operatorname{REDC}(t)\equiv tR^{-1}\pmod n$	REDC is not simply $t\bmod n$	What reduction is computed?
Conversion	Encode with $xR\bmod n$ and decode with REDC	Mixing domains corrupts products	How are boundaries crossed?

Step-by-Step Derivations and Algorithms

Precompute $n'\equiv-n^{-1}\pmod R$. For $0\le t\lt nR$, set

$$m=(tn')\bmod R,\qquad u=(t+mn)/R.$$

Because $t+mn\equiv t-tn^{-1}n\equiv0\pmod R$, division by $R$ is exact. Also $uR\equiv t\pmod n$, hence $u\equiv tR^{-1}\pmod n$. The input bound proves $0\le u\lt2n$, so one conditional subtraction canonicalizes the result.

For encoded operands, $\operatorname{REDC}(xR\cdot yR)\equiv xyR\pmod n$. Binary exponentiation stays encoded, using $R\bmod n$ as its multiplicative identity, and decodes only once at the end.

Montgomery Multiplication algorithm map

flowchart TD
    A[Validate odd modulus] --> B[Choose power-of-two radix R above n]
    B --> C[Compute negative inverse modulo R]
    C --> D[Encode operands]
    D --> E[Multiply encoded values]
    E --> F[Cancel low word with m times n]
    F --> G[Shift by radix bits]
    G --> H{Result at least n?}
    H -->|Yes| I[Subtract n once]
    H -->|No| J[Keep result]
    I --> K[Continue encoded or decode]
    J --> K

REDC preserves $u\equiv tR^{-1}\pmod n$; the negative inverse makes $t+mn$ exactly divisible by $R$, and $t\lt nR$ proves one subtraction suffices. For $k$ machine limbs, schoolbook Montgomery multiplication costs $O(k^2)$ word operations and binary exponentiation costs $O(k^2\log e)$.

Implementation, Complexity and Engineering

The reference selects the smallest power-of-two radix above the odd modulus, verifies the inverse invariant and REDC bound, and tests all conversions against ordinary modular arithmetic. Python is used for clarity; its arbitrary-precision operations and branches are not constant-time.

class MontgomeryContext:
    def __init__(self, modulus):
        if not isinstance(modulus, int) or isinstance(modulus, bool):
            raise TypeError("modulus must be an integer")
        if modulus <= 1 or modulus % 2 == 0:
            raise ValueError("modulus must be odd and greater than one")
        self.modulus = modulus
        self.bits = modulus.bit_length()
        self.radix = 1 << self.bits
        self.mask = self.radix - 1
        self.negative_inverse = (-pow(modulus, -1, self.radix)) & self.mask
        self.encoded_one = self.radix % modulus
        if (modulus * self.negative_inverse + 1) % self.radix:
            raise ArithmeticError("inverse invariant failed")

    def reduce(self, value):
        if not isinstance(value, int) or isinstance(value, bool):
            raise TypeError("REDC input must be an integer")
        if value < 0 or value >= self.modulus * self.radix:
            raise ValueError("REDC input is outside its bound")
        multiplier = value * self.negative_inverse & self.mask
        numerator = value + multiplier * self.modulus
        if numerator & self.mask:
            raise ArithmeticError("low word was not cancelled")
        result = numerator >> self.bits
        if result >= self.modulus:
            result -= self.modulus
        return result

    def encode(self, value):
        return value % self.modulus * self.radix % self.modulus

    def decode(self, value):
        return self.reduce(value % self.modulus)

    def multiply(self, left, right):
        product = left % self.modulus * (right % self.modulus)
        if product >= self.modulus * self.radix:
            raise ArithmeticError("product exceeds REDC bound")
        return self.reduce(product)

    def power(self, base, exponent):
        if not isinstance(exponent, int) or isinstance(exponent, bool):
            raise TypeError("exponent must be an integer")
        if exponent < 0:
            base = pow(base, -1, self.modulus)
            exponent = -exponent
        result = self.encoded_one
        factor = self.encode(base)
        while exponent:
            if exponent & 1:
                result = self.multiply(result, factor)
            factor = self.multiply(factor, factor)
            exponent >>= 1
        return self.decode(result)


context = MontgomeryContext(17)
assert context.radix == 32
assert context.negative_inverse == 15
assert context.encode(5) == 7
assert context.encode(7) == 3
encoded = context.multiply(context.encode(5), context.encode(7))
assert encoded == context.encode(1)
assert context.decode(encoded) == 1

for modulus in (3, 5, 17, 101, 65537, 1_000_000_007):
    current = MontgomeryContext(modulus)
    for left in (-9, 0, 1, 2, modulus - 1, modulus + 8):
        assert current.decode(current.encode(left)) == left % modulus
        for right in (-4, 0, 1, 3, modulus - 1):
            product = current.multiply(current.encode(left), current.encode(right))
            assert current.decode(product) == left * right % modulus
    for base in (-3, 0, 2, modulus - 1):
        for exponent in (0, 1, 2, 7, 63):
            assert current.power(base, exponent) == pow(base, exponent, modulus)

assert MontgomeryContext(101).power(7, -3) == pow(7, -3, 101)

for invalid in (0, 1, 2, 18, -7):
    try:
        MontgomeryContext(invalid)
    except ValueError:
        pass
    else:
        raise AssertionError("invalid modulus accepted")

try:
    context.reduce(context.modulus * context.radix)
except ValueError:
    pass
else:
    raise AssertionError("invalid REDC input accepted")

print("all tests passed")

Choice	Benefit or cost	Failure mode	Mitigation
Ordinary remainder	Simple for isolated operations	Division is costly in long chains	Convert once for repeated products
Montgomery reduction	Uses multiply-add, mask, shift	Requires odd modulus	Reject even moduli or use Barrett reduction
Smallest $R>n$	Compact bounds	Native products may require double width	Use wide types or limbs
Precomputed $n'$	Reused in every REDC	Wrong sign corrupts all results	Verify $nn'\equiv-1\pmod R$
Conditional subtraction	Produces canonical residue	Omitting it may return value at least $n$	Prove bound and subtract once
Explicit domain API	Prevents mixed operands	Raw integers hide their domain	Use distinct wrapper types
Branchless native code	Controls timing leakage	High-level code is not constant-time	Use audited low-level primitives

Applications, Case Studies and Exercises

For $n=17$, $R=32$, and $n'=15$, the encoded product of $5$ and $7$ is based on raw value $21$. REDC chooses $m=27$ and computes $(21+27\cdot17)/32=15$, the encoding of $1$. A production benchmark should separate one-time setup and conversion from steady-state multiplication across several operand sizes.

Practice

Apply Montgomery Multiplication

Case study 1. Trace $n=17$, $R=32$, $n'=15$, $x=5$, and $y=7$. Record encodings, raw product, cancellation multiplier, divisible numerator, shift, and decode. Success means every invariant holds and the result is $1$.

Case study 2. Benchmark reproducible odd moduli near $32$, $64$, $128$, and $256$ bits. Verify at least $10{,}000$ products, then time exponentiation while reporting setup, conversion, and steady-state costs separately. Success requires exact agreement and a measured crossover.

Exercises. Prove exact divisibility and the $2n$ bound; add fixed-window exponentiation; test the wrong inverse sign, missing subtraction, and domain mixing; implement a limb-oriented constant-time REDC under a documented word model.

Use ordinary reduction for isolated operations, Barrett reduction when even moduli must be supported, and Montgomery form for long chains under one odd modulus. Never mix domains, omit the REDC bound, or claim constant-time behavior from high-level code; those boundaries define reliable cryptographic arithmetic.

Cookie Consent