The modulus 0 < M < 2^W_M occupies a register of W_M-bits width:

	←WM→
	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
	↜JM↝

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 < BM < 2KM
	←2WM→
	0	BM
	↜JM↝	↜2WM - JM↝

0 ≤ X < 2^K_M is the integer to be reduced modulo M, and occupies a register of twice the bitness of the register containing M:

	X
	←2WM→

1: X_s = X >> J_M

	0	XS
	↜JM↝	↜2WM - JM↝

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	XS
×	0	BM
	←4WM→
=	0		Z
	↜2JM↝		↜4WM - 2JM↝

3: Z_s := Z >> 2W_M - J_M

	←4WM→
	0	ZS
		↜2WM - JM↝

	←2WM→
	0	ZS
		↜2WM - JM↝

4: Q := Z_s × M

		0	ZS
×				0	M
	←3WM→
=	0	Q
			←2WM→