給定多項式
F
(
x
)
F(x)
F(x)和
G
(
x
)
G(x)
G(x)，求
F
(
x
)
F(x)
F(x)除以
G
(
x
)
G(x)
G(x)的商
Q
(
x
)
Q(x)
Q(x)和餘數
R
(
x
)
R(x)
R(x)。即
F
(
x
)
=
Q
(
x
)
G
(
x
)
+
R
(
x
)
D
e
g
(
R
)
<
D
e
g
(
G
)
<
D
e
g
(
F
)
F(x)=Q(x)G(x)+R(x)\quad Deg(R)<Deg(G)<Deg(F)
F(x)=Q(x)G(x)+R(x)Deg(R)<Deg(G)<Deg(F)
首先構造
F
R
(
x
)
=
x
D
e
g
(
F
)
F
(
1
x
)
F^R(x)=x^{Deg(F)}F(\frac{1}{x})
FR(x)=xDeg(F)F(x1)
這個東西就是將係數反轉。比如
F
(
x
)
=
x
4
+
2
x
3
+
3
x
2
+
4
x
+
5
F
R
(
x
)
=
5
x
4
+
4
x
3
+
3
x
2
+
2
x
1
\begin{aligned} F(x)&=x^4+2x^3+3x^2+4x+5\\ F^R(x)&=5x^4+4x^3+3x^2+2x1 \end{aligned}
F(x)FR(x)=x4+2x3+3x2+4x+5=5x4+4x3+3x2+2x1
令
n
=
D
e
g
(
F
)
,
m
=
D
e
g
(
G
)
n=Deg(F),m=Deg(G)
n=Deg(F),m=Deg(G)，則
n
−
m
=
D
e
g
(
Q
)
n-m=Deg(Q)
n−m=Deg(Q)
那麼就有
F
(
x
)
=
Q
(
x
)
G
(
x
)
+
R
(
x
)
x
n
F
(
x
)
=
x
n
Q
(
x
)
G
(
x
)
+
x
n
R
(
x
)
x
n
F
(
1
x
)
=
x
n
−
m
Q
(
1
x
)
x
m
G
(
1
x
)
+
x
n
−
m
+
1
x
m
−
1
R
(
1
x
)
F
R
(
x
)
=
Q
R
(
x
)
G
R
(
x
)
+
x
n
−
m
+
1
x
m
−
1
R
(
1
x
)
F
R
(
x
)
≡
Q
R
(
x
)
G
R
(
x
)
m
o
d
x
n
−
m
+
1
F
R
(
x
)
[
G
R
(
x
)
]
−
1
≡
Q
R
(
x
)
m
o
d
x
n
−
m
+
1
\begin{aligned} F(x)&=Q(x)G(x)+R(x)\\ x^nF(x)&=x^nQ(x)G(x)+x^nR(x)\\ x^nF(\frac{1}{x})&=x^{n-m}Q(\frac{1}{x})x^mG(\frac{1}{x})+x^{n-m+1}x^{m-1}R(\frac{1}{x})\\ F^R(x)&=Q^R(x)G^R(x)+x^{n-m+1}x^{m-1}R(\frac{1}{x})\\ F^R(x)&\equiv Q^R(x)G^R(x)\;mod\;x^{n-m+1}\\ F^R(x)[G^R(x)]^{-1}&\equiv Q^R(x)\;mod\;x^{n-m+1} \end{aligned}
F(x)xnF(x)xnF(x1)FR(x)FR(x)FR(x)[GR(x)]−1=Q(x)G(x)+R(x)=xnQ(x)G(x)+xnR(x)=xn−mQ(x1)xmG(x1)+xn−m+1xm−1R(x1)=QR(x)GR(x)+xn−m+1xm−1R(x1)≡QR(x)GR(x)modxn−m+1≡QR(x)modxn−m+1
現在我們求出了在模
x
n
−
m
+
1
x^{n-m+1}
xn−m+1意義下
Q
R
(
x
)
Q^R(x)
QR(x)的解，則
Q
R
(
x
)
=
F
R
(
x
)
[
G
R
(
x
)
]
−
1
m
o
d
x
n
−
m
+
1
+
a
n
−
m
+
1
x
n
−
m
+
1
+
a
n
−
m
+
2
x
n
−
m
+
2
+
.
.
.
Q^R(x)=F^R(x)[G^R(x)]^{-1}\;mod\;x^{n-m+1}+a_{n-m+1}x^{n-m+1}+a_{n-m+2}x^{n-m+2}+...
QR(x)=FR(x)[GR(x)]−1modxn−m+1+an−m+1xn−m+1+an−m+2xn−m+2+...
但又因為
D
e
g
(
G
R
)
=
D
e
g
(
G
)
=
n
−
m
<
n
−
m
+
1
Deg(G^R)=Deg(G)=n-m<n-m+1
Deg(GR)=Deg(G)=n−m<n−m+1，所以
Q
R
(
x
)
=
F
R
(
x
)
[
G
R
(
x
)
]
−
1
m
o
d
x
n
−
m
+
1
Q^R(x)=F^R(x)[G^R(x)]^{-1}\;mod\;x^{n-m+1}
QR(x)=FR(x)[GR(x)]−1modxn−m+1