無平方多項式

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

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

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

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

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

Yun演算法

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

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

若

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

是想要的分解，因此令

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

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

和

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

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

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

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

和

${\displaystyle 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}.}$

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

演算法可以表示如下：

${\displaystyle 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;}$
重複
${\displaystyle 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}';}$
直到${\displaystyle b_{i}=1;}$為止
輸出${\displaystyle a_{1},\ldots ,a_{i-1}.}$

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

平方根

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

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

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