사각 프리 다항식

수학에서 사각형 없는 다항식은 일정하지 않은 다항식의 어떤 사각형도 구분자로 가지지 않는 필드(또는 보다 일반적으로는 적분 영역)에 걸쳐 정의되는 다항식이다.^[1]일변량 다항식은 계수를 포함하는 대수적으로 폐쇄된 필드에 복수 루트가 없는 경우에만 제곱이 자유롭다.이것은 물리학과 공학에서 사각형 없는 다항식을 반복된 뿌리가 없는 다항식이라고 부르는 동기를 부여한다.null

일변량 다항식의 경우 p가² f를 나누면 p가 형식 파생상품 f를 f의 '로 나눈다는 것을 제품 규칙이 내포하고 있다.역행은 특성 0에서도, 유한한 필드(또는 보다 일반적으로는 완벽한 필드)에 대한 다항식에서도 적용된다.즉, 이 경우 다항식 1이 다항식 및 그 파생상품의 가장 큰 공통점인 경우에만 다항식은 제곱이 없는 것이다.null

다항식의 정사각형 없는 분해 또는 정사각형 없는 인자화는 정사각형 없는 다항식의 힘으로 인자를 만드는 것이다.

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

여기서_k, a의 값이 쌍으로 이루어진 복사 제곱이 없는 다항식(여기서, 두 개의 다항식이 그들의 가장 큰 공통점이라고 한다. 즉, 고려된 계수의 분수 영역에 대한 동일성이다.)^[1]이다.0이 아닌 모든 다항식에서는 제곱이 없는 인자화를 인정하는데, 이는 0이 아닌 상수에 의한 인자의 곱과 나눗셈에 따라 고유한 것이다.정사각형이 없는 인자화는 수정 불가능한 인자로의 완전한 인자화보다 계산하기가 훨씬 쉬우며, 따라서 부분분수분해와 합리적인 분수의 상징적 통합에 관해서는 완전한 인자화가 실제로 필요하지 않을 때 종종 선호된다.사각 자유 인자화는 컴퓨터 대수 시스템에서 구현되는 다항식 인자화 알고리즘의 첫 번째 단계다.따라서 컴퓨터 대수학에서는 사각 자유 인자화 알고리즘이 기본이다.null

특성 0의 영역에 걸쳐, 그것의 GCD와 그것의 파생상품에 의한$$ $f{\displaystyle }$ ${\displaystyle f}$의 몫은 위의 사각형 없는 ${\displaystyle {분해}_{}}$에서 $i{\displaystyle {}_{}}$ ${\$의 산물이다.0이 아닌 특성 p의 완벽한 필드 위에 이 지수는 p의$$배수가 $아닌$ i {\$displaystyle$ a_$${$i}$의 곱이다.추가 GCD 연산 및 정확한 구획을 통해 정사각형 자유 인자화(한계 영역에 대한 정사각형 자유 인자화 참조)를 계산할 수 있다.특성 0에서는 아래에 기술된 윤의 알고리즘인 더 나은 알고리즘이 알려져 있다.^[1]그것의 계산 복잡성은 입력 다항식 및 파생상품의 GCD 계산의 최대 두 배다.좀 더 정확히 $말하면{\displaystyle }$ ${\displaystyle {Tn}_{}}${\$displaystyle T_{n}}$가 도 n ${\displaystyle n}$의 두 다항식 GCD 계산에 필요한 시간이고$$ GCD에 의한 이러한 다항식의 몫이라면 ${\displaystyle {2Tn}_{}}$ ${\$은 제곱 자유분해 계산에 필요한 시간의 상한이다$$.null

다변량 다항식의 정사각형 없는 분해 계산을 위한 알고리즘도 있는데, 다항식 다항식 계수를 갖는 일변량 다항식으로서 다변량 다항식 다항식을 고려하고, 재귀적으로 일변량 알고리즘을 적용함으로써 일반적으로 진행된다.^[2]null

윤의 알고리즘

이 절에서는 특성 0의 필드에 걸쳐 일변량 다항식의 제곱이 없는 분해에 대한 윤의 알고리즘을 설명한다.^[1]GCD 연산과 정확한 분할에 의해 진행된다.null

따라서 입력은 0이 아닌 다항식 f이며, 알고리즘의 첫 번째 단계는 GCD a₀ of f와 그것의 공식 파생 f'를 계산하는 것으로 구성된다.null

만약

${\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}^{k}ia_{i}'a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

$b{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle f{}_{}}$ /${\displaystyle {0\mathrm{}}_{}}$ ${\$$0$$\}\},$ $c{\displaystyle {}_{}{1\mathrm{}}_{}}$ = ${\displaystyle {}^{}/}$ / ${\displaystyle {0\mathrm{}}_{}}${\$displaystyle c_{1}=f'/a_$${0},$ $d{\displaystyle {}_{}{}_{}}$= ${\displaystyle {b\mathrm{}}_{}^{}}$ 1${\displaystyle {}_{}^{}}${ ${\$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_{2}\cdots a_{i-1a_{i+1}\cdots a_{k}.}$

${\displaystyle {\mathrm{b}}_{}}$ ${\displaystyle k_{}}$+ 1${\displaystyle {}_{}}$= ${\displaystyle 1}$ ${\displaystyle b_{k+1}=1}$까지 이 프로세스를 반복하면 ${\displaystyle {모든}_{}}$ i${\displaystyle {}_{}}$. ${\displaystyle a_{i$}를 찾을 수 있다$.$$}$

이는 다음과 같이 알고리즘으로 공식화된다.

${\displaystyle a_{0}=\gcd(f,f');\cdb_{1}:=f/a_{0};\properties c_{1}=f'/a_{0};\put d_{1}=c_{1}-b_{1};\put i:=1;}$
되풀이하여 말하다
${\displaystyle a_{i}:=\gcd(b_{i},d_{i});\cd b_{i+1}:=b_{i}/a_{i},\csn c_{i}/d_{i}:d_{i}/a_{i},\c.==i}-b_{i};};};},}$
$b{\displaystyle }$= ${\displaystyle 1;}$ ${\displaystyle b=1;}$까지
${\displaystyle {출력\mathrm{}}_{}}$ $a{\displaystyle {}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle a_{}}$ -${\displaystyle 1_{}}$. ${\displaystyle a_{1},\ldots ,a_{i-1}.$$}$

$c{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$와 ${\displaystyle {di}_{}}$ ${\$의 정도는 ${\displaystyle b_{}}$ i${\displaystyle {}_{}}$ ${\displaystyle b_{i}$의 정도보다 한 수 적다$$.$}$ ${\displaystyle f}$이(가$)$ $b{\displaystyle {}_{}{i}_{}}$의 산물인$$ $것$처럼, {\$displaystyle$ b_{$i$$}$의 도 합은$$ $f{\displaystyle .}$ ${\displaystyle$$f.}$GCD$$ 계산과 구획의 복잡성이 도에 따라 선형으로 증가함에 따라$$ 총 가동 시간이 경과하게 된다$.$"반복" 루프는 알고리즘의 첫 번째 라인의 실행 시간보다 작으며, 윤 알고리즘의 총 실행 시간은 $f{\displaystyle }$ ${\displaystyle$ f$}$및 $f{\displaystyle {}^{}}$′ ${\$ f$'$의 GCD 계산에$$ 필요한 시간의 두 배와 $f{\displaystyle }$ ${\displaystyle f}$와 $f$ ′ ${\$의 몫으로 상한 값이다.$$ 그들의 GCD에 의해.null

제곱근

일반적으로 다항식에는 제곱근이 없다.더 정확히 말하면, 대부분의 다항식은 다른 다항식의 제곱으로 쓸 수 없다.null

다항식은 제곱이 없는 분해의 모든 지수가 짝수인 경우에만 제곱근을 가진다.이 경우 제곱근은 이러한 지수 2로 나누어 얻는다.null

따라서 다항식이 제곱근을 가지고 있는지 여부를 결정하고, 다항식이 존재한다면 이를 계산하는 문제는 제곱 없는 인수화의 특수한 경우다.null

메모들

참조