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−1aixi≫k):=∑i=kn−1aixi−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−1aixi):=∑i=0min(k,n)−1aixi
最后，做逆映射
f
g
=
f
g
‾
R
−
1
m
o
d
h
fg = overline{f g} R^{-1} mod h
fg=fgR−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：将多项式模乘运算，转化为多项式乘法、“截断”以及“右移”。