数学裡的無平方多項式（）是指在域或是整环上的單變數多項式，在包括其係數的代數閉域內，沒有重根。在特征為0的域，或是有限域中，單變數多項式是無平方因式，若且唯若其無法被任何的平方所。在物理學和工程上，會將無平方多項式稱為沒有重根的多項式。
根據乘积法则，若除以可以整除，則的除以也可以整除。反之亦然，因此f是無平方多項式若且唯若1是多項式和其導數的最大公因式。
多項式的無平方分解（square-free decomposition）或無平方因次分解是指將多項式分解為無平方多項式的次幂
:
f = a_1 a_2^2 a_3^3 \cdots a_n^n =\prod_{k=1}^n a_k^k\,
其中不是整數的都是無平方多項式，且彼此之間的最大公因式為1（稱為互質）。
Yun演算法
Yun演算法可以針對特征為0的域上的多項式，進行無平方分解，其作法會進行許多的最大公因式計算以及多項式除法。
其輸入是非零的多項式f，第一步是計算f和其 f的最大公因式a*0
若
:
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 i a_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。
演算法可以表示如下：
{{quotation|
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就是多項式的平方根。
因此判斷一個多項式是否有平方根，就變成無平方分析裡的一個特例。
參考資料
评论 (0)