- * The result of a Montgomery reduction of %$x$% is %$x R^{-1} \bmod m$%,
- * which doesn't look ever-so useful. The trick is to initially apply a
- * factor of %$R$% to all of your numbers so that when you multiply and
- * perform a Montgomery reduction you get %$(x R \cdot y R) R^{-1} \bmod m$%,
- * which is just %$x y R \bmod m$%. Thanks to distributivity, even additions
- * and subtractions can be performed on numbers in this form -- the extra
- * factor of %$R$% just runs through all the calculations until it's finally
- * stripped out by a final reduction operation.
+ * Suppose that %$0 \le a_i \le (b^n + b^i - 1) m$% with %$a_i \equiv {}$%
+ * %$0 \pmod{b^i}$%. Let %$w_i = m' a_i/b^i \bmod b$%, and set %$a_{i+1} =
+ * a_i + b^i w_i m$%. Then obviously %$a_{i+1} \equiv {} $% %$a_i
+ * \pmod{m}$%, and less obviously %$a_{i+1}/b^i \equiv a_i/b^i + {}$% %$m m'
+ * a_i/b^i \equiv 0 \pmod{b}$% so %$a_{i+1} \equiv 0 \pmod{b^{i+1}}$%.
+ * Finally, we can bound %$a_{i+1} \le {}$% %$a_i + b^i (b - 1) m = {}$%
+ * %$a_i + (b^{i+1} - b^i) m \le (b^n + b^{i+1} - 1) m$%. As a result, if
+ * we're given some %a_0%, we can calculate %$a_n \equiv 0 \pmod{R}$%, with
+ * $%a_n \equiv a_0 \pmod{n}$%, i.e., %$a_n/R \equiv a_0 R^{-1} \pmod{m}$%;
+ * furthermore, if %$0 \le a_0 < m + b^n%$ then %$0 \le a_n/R < 2 m$%, so a
+ * fully reduced result can be obtained with a single conditional
+ * subtraction.
+ *
+ * The result of reduing %$a$% is then %$a R^{-1}$% \bmod m$%. This is
+ * actually rather useful for reducing products, if we run an extra factor of
+ * %$R$% through the calculation: the result of reducing the product of
+ * %$(x R)(y R) = x y R^2$% is then %$x y R \bmod m$%, preserving the running
+ * factor. Thanks to distributivity, additions and subtractions can be
+ * performed on numbers in this form -- the extra factor of %$R$% just runs
+ * through all the calculations until it's finally stripped out by a final
+ * reduction operation.