給定多項式
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+1?xn?m+1+an?m+2?xn?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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/188740.html
標籤：python