1. modular reduction模简化定义

modular reduction模简化的定义为：
若z为任意整数，则 z mod m 的结果在区间[0, m-1]，相当于z除以m的余数，该运算过程称为z对模m的模简化。

2. 模运算

有限域Z_m内的加减乘除运算，其中的m为多精度正整数，m称为模。

将正整数m，非负整数x,y (x<m y<m)以b进制格式表示：
m=(m_nm_n-1…m₁m₀)_b
x=(x_nx_n-1…x₁x₀)_b
y=(y_ny_n-1…y₁y₀)_b

模运算：

• 模加法：x + y mod m
• 模减法：x - y mod m
• 模乘法：x * y mod m
• 模取反：x^-1 mod m

2.1 模加法和模减法

对于常规的多精度运算来说，模加法和模减法为最简单的运算。

举例：
当0<x<m, 0<y<m时，则有：
1）x+y < 2m;
2) 若x >= y，则0 =< x-y < m;
3) 若x <y，则有0 =< x+m-y < m.

因此对于模加法和模减法，可分别采用参考资料1中的$14.7算法（当x+y>=m时，需额外增加一步-m的操作）和$14.9算法（当x >= y）。

2.2 乘法运算

以b进制表示：
x=(x_nx_n-1…x₁x₀)_b 【n+1位】
y=(y_ty_t-1…y₁y₀)_b 【t+1位】
则 x*y 的乘积结果以b进制表示，最多有(n+t+2)位。

小学笔算级别求乘积的算法如下：

举例：

2.3 除法运算

除法运算为基础多精度加减乘除运算中最复杂且最耗时的运算。
以下算法为计算x除以y的商q和余数r，即：
x=y*q+r, 0=<r<y

2.4 模乘法

模乘法既需要2.2中的乘法运算，也需要第一节中提到的模简化运算。

2.4.1 模乘法classical算法

传统直观的求解模乘法x*y mod m的算法可分解为：
1）用2.2乘法运算求得xy；
2）用2.3除法运算球的xy除以m的余数r;
3）返回r值。

该算法简单直接，但效率不高。

2.4.2 模乘法Montgomery reduction算法

参考资料：
[1] The Montgomery reduction here is based on Algorithm 14.32 in Handbook of Applied Cryptography chap14 http://cacr.uwaterloo.ca/hac/about/chap14.pdf.