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 p 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 k 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 k k，使得 f ? e f \cdot e f?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 p p是素數，計算： f ? g m o d ?? h f \cdot g \mod h f?gmodh

首先，尋找 R = x k ∈ Z p [ x ] R=x^k \in Z_p[x] R=xk∈Zp?[x]，其中 k k k是某個正整數，使得 g c d ( R , h ) = 1 gcd(R,h)=1 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 ∣ T + m h R \mid T+mh R∣T+mh
那么
T + m h ≡ 0 m o d ?? R T+mh \equiv 0 \mod R T+mh≡0modR
從而
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 k值，結果都是正確的，但如果 k < n k<n k<n，計算出的結果可能是冗余的，

總結

• Barrett reduction of polynomials：將多項式取模運算，轉化為多項式乘法以及“右移”，
• Montgomery multiplication of polynomials：將多項式模乘運算，轉化為多項式乘法、“截斷”以及“右移”，