Barrett And Montgomery of Polynomials

Barrett reduction of polynomials

对于 f , g ∈ Z p [ x ] f,g in Z_p[x] f,g∈Zp​[x]，其中$p$是素数。那么：
f m o d    g = f − ⌊ f g ⌋ g f mod g = f - lfloor frac{f}{g} rfloor g fmodg=f−⌊gf​⌋g
其中的分式属于分式域： 1 / g ∈ { f g ∣ f , g ∈ Z p [ x ] } 1/g in { dfrac{f}{g} | f,g in Z_p[x] } 1/g∈{gf​∣f,g∈Zp​[x]}

我们寻找一个 m ∈ Z p [ x ] m in Z_p[x] m∈Zp​[x]，使得：
1 g = m R frac{1}{g} = frac{m}{R} g1​=Rm​
其中， R = x k ∈ Z p [ x ] R=x^k in Z_p[x] R=xk∈Zp​[x]，$k$是某个正整数

那么选取：
m = ⌊ R g ⌋ ∈ Z p [ x ] m = lfloor frac{R}{g} rfloor in Z_p[x] m=⌊gR​⌋∈Zp​[x]
误差大小为：
e = 1 g − ⌊ R g ⌋ R e = frac{1}{g} - dfrac{lfloor frac{R}{g} rfloor}{R} e=g1​−R⌊gR​⌋​
于是，
f m o d    g ≈ f − ⌊ f ⋅ m R ⌋ g f mod g approx f - lfloor frac{f cdot m}{R} rfloor g fmodg≈f−⌊Rf⋅m​⌋g
选取足够大的$k$，使得$f\cdot e$的系数足够小，那么：
f m o d    g = f − ( ( f ⋅ m ) ≫ k ) g ∈ Z p [ x ] f mod g = f - ((f cdot m) gg k) g in Z_p[x] fmodg=f−((f⋅m)≫k)g∈Zp​[x]
这里的$\gg$运算定义为 ( ∑ i = 0 n − 1 a i x i ≫ k ) : = ∑ i = k n − 1 a i x i − k (sum_{i=0}^{n-1}a_i x^i gg k) := sum_{i=k}^{n-1}a_i x^{i-k} (∑i=0n−1​ai​xi≫k):=∑i=kn−1​ai​xi−k

Montgomery multiplication of polynomials

对于 f , g , h ∈ Z p [ x ] f,g,h in Z_p[x] f,g,h∈Zp​[x]，其中$p$是素数。计算：$f\cdot g\mathrm{m}\mathrm{o}\mathrm{d}h$

首先，寻找 R = x k ∈ Z p [ x ] R=x^k in Z_p[x] R=xk∈Zp​[x]，其中$k$是某个正整数，使得$gcd(R,h)=1$

计算：
h − 1 ⋅ h ≡ 1 m o d    R R − 1 ⋅ R ≡ 1 m o d    h h^{-1} cdot h equiv 1 mod R\ R^{-1} cdot R equiv 1 mod h\ h−1⋅h≡1modRR−1⋅R≡1modh
做可逆映射：
f ‾ = f R m o d    h g ‾ = g R m o d    h overline{f} = f R mod h\ overline{g} = g R mod h\ f​=fRmodhg​=gRmodh
那么
f g ‾ = f g R = f ‾ ⋅ g ‾ ⋅ R − 1 m o d    h overline{f g} = f g R = overline{f} cdot overline{g} cdot R^{-1} mod h fg​=fgR=f​⋅g​⋅R−1modh
简记 T = f ‾ ⋅ g ‾ T = overline{f} cdot overline{g} T=f​⋅g​，则 f g ‾ = T R − 1 overline{f g} = TR^{-1} fg​=TR−1

寻找 m ∈ Z p [ x ] m in Z_p[x] m∈Zp​[x]，使得
$$R\mid T+mh$$
那么
$$T+mh\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}R$$
从而
m = − T h − 1 m o d    R m = -Th^{-1} mod R m=−Th−1modR
于是
f g ‾ ≡ ( T + m h ) R − 1 = ( T − ( T h − 1 m o d    R ) ⋅ h ) ⋅ R − 1 m o d    h overline{f g} equiv (T+mh)R^{-1} = (T-(Th^{-1} mod R) cdot h) cdot R^{-1} mod h fg​≡(T+mh)R−1=(T−(Th−1modR)⋅h)⋅R−1modh
由于 R = x k R=x^k R=xk，所以
f g ‾ = ( T − L o w k ( T h − 1 ) ⋅ h ) ≫ k overline{f g} = (T-Low_k(Th^{-1}) cdot h) gg k fg​=(T−Lowk​(Th−1)⋅h)≫k
这里定义 L o w k ( ∑ i = 0 n − 1 a i x i ) : = ∑ i = 0 min ⁡ ( k , n ) − 1 a i x i Low_k(sum_{i=0}^{n-1}a_i x^i) := sum_{i=0}^{min(k,n)-1}a_i x^i Lowk​(∑i=0n−1​ai​xi):=∑i=0min(k,n)−1​ai​xi

最后，做逆映射 f g = f g ‾ R − 1 m o d    h fg = overline{f g} R^{-1} mod h fg=fg​R−1modh，计算方法与上述的计算 T R − 1 m o d    h TR^{-1} mod h TR−1modh的过程相同。其实叫做：Montgomery reduction

与Barrett不同，这里选取任意的$k$值，结果都是正确的。但如果$k<n$，计算出的结果可能是冗余的。

总结

• Barrett reduction of polynomials：将多项式取模运算，转化为多项式乘法以及“右移”。
• Montgomery multiplication of polynomials：将多项式模乘运算，转化为多项式乘法、“截断”以及“右移”。