The modulus 0 < M < 2^{WM} occupies a register of W_{M}-bits width:
←W_{M}→ | |
M |
We will use ↜curly arrows↝ to refer to the widths of hypothetical zero and nonzero segments of registers, for the purpose of min/max width analysis of the intermediate results in our computation.
0 ≤ J_{M} < W_{M} is one less than the measure of M:
0 | M | |
↜J_{M}↝ |
Lemma 1: For any integers A ≥ 0, B > 0, C = ⌊A / B⌋, Measure(C) ≤ Measure(A) - Measure(B) + 1.
Therefore, Measure of B_{M} will be less than or equal to:
2W_{M} - Measure(M) + 1 = 2W_{M} - J_{M}
0 < B_{M} < 2^{KM} | ||
←2W_{M}→ | ||
0 | B_{M} | |
↜J_{M}↝ | ↜2W_{M} - J_{M}↝ |
0 ≤ X < 2^{KM} is the integer to be reduced modulo M, and occupies a register of twice the bitness of the register containing M:
X | |
←2W_{M}→ |
1: X_{s} = X >> J_{M}
0 | X_{S} | |
↜J_{M}↝ | ↜2W_{M} - J_{M}↝ |
Lemma 2: For any integers A ≥ 0, B ≥ 0, C = A × B, Measure(C) ≤ Measure(A) + Measure(B).
2: Z := X_{s} × B_{M}
0 | X_{S} | ||||
× | 0 | B_{M} | |||
←4W_{M}→ | |||||
= | 0 | Z | |||
↜2J_{M}↝ | ↜4W_{M} - 2J_{M}↝ |
3: Z_{s} := Z >> 2W_{M} - J_{M}
←4W_{M}→ | ||
0 | Z_{S} | |
↜2W_{M} - J_{M}↝ |
←2W_{M}→ | ||
0 | Z_{S} | |
↜2W_{M} - J_{M}↝ |
4: Q := Z_{s} × M
0 | Z_{S} | ||||
× | 0 | M | |||
←3W_{M}→ | |||||
= | 0 | Q | |||
←2W_{M}→ |