無平方多項式

数学裡的無平方多項式（英語：square-free polynomial）是指在域或是整环上的單變數多項式，在包括其係數的代數閉域內，沒有重根。在特征為0的域，或是有限域中，單變數多項式是無平方因式，若且唯若其無法被任何非常數多項式的平方所整除（英语：divisibility (ring theory)）^[1]。在物理學和工程上，會將無平方多項式稱為沒有重根的多項式。

根據乘积法则，若 $f$ 除以 $p 2$ 可以整除，則 $f$ 的形式導數（英语：formal derivative） $f'$ 除以 $p$ 也可以整除。反之亦然，因此 $f$ 是無平方多項式若且唯若 $1$ 是多項式和其導數的最大公因式^[2]。

多項式的無平方分解（square-free decomposition）或無平方因次分解是指將多項式分解為無平方多項式的次幂

f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{n}^{n}=\prod _{k=1}^{n}a_{k}^{k}\,

其中不是整數的 $a k$ 都是無平方多項式，且彼此之間的最大公因式為1（稱為互質）^[1]。每一個非零的多項式都有一個無平方分解，且是唯一的（頂多會差異一個非零常係數的相乘或相除）。無平方分解比多項式的完整多項式分解（英语：polynomial factorization）（各項是不可约多项式）要簡單。因此在不需要完整多項式分解時會用此方式代替，像是部分分式分解以及代數分式的符号积分。在計算機代數系統的多項式分解演算法中，無平方分解是第一步。因此無平方分解是計算機代數的基礎。

在特征為0的域中，用 $f$ 去除以 $f$ 和導數的最大公因式（GCD）, 其商是上面無平方分解的 $a_{i}$ 乘積。在非零特徵 $p$ 的完美域（英语：perfect field）中，其商是 $a_{i}$ 的乘積，而 $i$ 不是 $p$ 的倍數。進一步的最大公因式計算以及實際的除法，可以計算無平方分解。在特徵為0的域中，已有比較好的算法，就是以下的Yun演算法^[1]。其運算複雜度（英语：computational complexity）最多會是輸入多項式以及其導數GCD計算量的兩倍。準確的說，若 $T_{n}$ 是計算二個 $n$ 次多項式最大公因式需要的時間，則 $2T_{n}$ 就是計算其無平方分解時間的上限。

也有已知的演算法可以計算多變數多項式的無平方分解，作法是將多變數多項式視為是有單變數多項式，但其係數是由多項式組成，接著遞迴的使用單變數下的演算法^[3]。

Yun演算法

Yun演算法可以針對特征為0的域上的多項式，進行無平方分解^[1]，其作法會進行許多的最大公因式計算以及多項式除法。

其輸入是非零的多項式f，第一步是計算f和其形式導數（英语：formal derivative） f'的最大公因式a₀

若

f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{k}^{k}

是想要的分解，因此令

a_{0}=a_{2}^{1}a_{3}^{2}\cdots a_{k}^{k-1},

f/a_{0}=a_{1}a_{2}a_{3}\cdots a_{k}

和

f'/a_{0}=\sum _{i=1}^{k}ia_{i}'a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}.

若令 $b_{1}=f/a_{0}$ 、 $c_{1}=f'/a_{0}$ 和 $d_{1}=c_{1}-b_{1}'$ ，可得

\gcd(b_{1},d_{1})=a_{1},

b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},

和

c_{2}=d_{1}/a_{1}=\sum _{i=2}^{k}(i-1)a_{i}'a_{2}\cdots a_{i-1}a_{i+1}\cdots a_{k}.

重複上述步驟，直到 $b_{k+1}=1$ 為1為止，就找到所有的 $a_{i}$ 。

演算法可以表示如下：

$a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;$
重複
$a_{i}:=\gcd(b_{i},d_{i});\quad b_{i+1}:=b_{i}/a_{i};\quad c_{i+1}:=d_{i}/a_{i};\quad i:=i+1;\quad d_{i}:=c_{i}-b_{i}';$
直到 $b_{i}=1;$ 為止
輸出 $a_{1},\ldots ,a_{i-1}.$

$c_{i}$ 和 $d_{i}$ 的次數都比 $b_{i}$ 的次數少1。 $f$ 是 $b_{i}$ 的乘積， $b_{i}$ 次數的總和就是 $f$ 的次數。因為GCD計算和除法的複雜度都和多項式次數有關，成長速度比線性要快。因此迴圈的總執行時間少於演算法第一行進行所需的時間。Yun演算法的總執行時間上限是計算 $f$ 和 $f'$ 的最大公因式，以及計算除法總時間的兩倍。

平方根

一般來說，多項式不會有多項式的平方根，大部份的多項式無法用另一個多項式的平方來表示。

多項式有平方根若且唯若所有無平方分解的次方都是偶數，此時，將次方除以2就是多項式的平方根。

因此判斷一個多項式是否有平方根，就變成無平方分析裡的一個特例。

參考資料

^ ^1.0 ^1.1 ^1.2 ^1.3 Yun, David Y.Y. On square-free decomposition algorithms. SYMSAC '76 Proceedings of the third ACM Symposium on Symbolic and Algebraic Computation. Association for Computing Machinery. 1976: 26–35. ISBN 978-1-4503-7790-4. S2CID 12861227. doi:10.1145/800205.806320.
^ Dummit, David S.; Foote, Richard M. Abstract Algebra. 2004: 547. ISBN 978-81-265-3228-5.
^ Gianni, P.; Trager, B. Square-Free Algorithms in Positive Characteristic. Applicable Algebra in Engineering, Communication and Computing. 1996, 7 (1): 1–14. S2CID 36886948. doi:10.1007/BF01613611.

[yun-1] 1.0 ^1.1 ^1.2 ^1.3 Yun, David Y.Y. On square-free decomposition algorithms. SYMSAC '76 Proceedings of the third ACM Symposium on Symbolic and Algebraic Computation. Association for Computing Machinery. 1976: 26–35. ISBN 978-1-4503-7790-4. S2CID 12861227. doi:10.1145/800205.806320.

[2] Dummit, David S.; Foote, Richard M. Abstract Algebra. 2004: 547. ISBN 978-81-265-3228-5.

[gianni-3] Gianni, P.; Trager, B. Square-Free Algorithms in Positive Characteristic. Applicable Algebra in Engineering, Communication and Computing. 1996, 7 (1): 1–14. S2CID 36886948. doi:10.1007/BF01613611.

[1]

[2]

[3]

查论编多項式
函數	零次函數(常數函數) 一次函數二次函数三次函數四次函數五次函數
方程	一次方程二次方程三次方程四次方程五次方程六次方程七次方程八次方程
算法	多项式除法因式不可约多项式最大公因式秦九韶算法結式判别式