无平方多项式

数学里的无平方多项式（英语：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就是多项式的平方根。

因此判断一个多项式是否有平方根，就变成无平方分析里的一个特例。