다항식의 인자화

수학 및 컴퓨터 대수에서 다항식 또는 다항식 인자화의 인자화는 주어진 분야나 정수에 계수가 있는 다항식을 같은 영역에 계수를 갖는 계수를 갖는 불가역 인자의 산물로 표현한다. 다항식 인자화는 컴퓨터 대수 시스템의 기본 구성요소 중 하나이다.

최초의 다항식 인자화 알고리즘은 1793년 테오도르 폰 슈베르트에 의해 발표되었다.^[1] 레오폴트 크로네커는 1882년 슈베르트의 알고리즘을 재발견하여 대수적 확장에서 다변량 다항식과 계수로 확장했다. 그러나 이 주제에 대한 대부분의 지식은 1965년 경과 최초의 컴퓨터 대수학 시스템보다 오래되지 않았다.

오랫동안 알려진 유한 단계 알고리즘이 처음으로 컴퓨터에 적용되었을 때, 그것들은 매우 비효율적인 것으로 밝혀졌다. 컴퓨터 시간 몇 분 안에 100도까지의 정도와 적당한 크기의 계수(최대 100비트)를 가진 거의 모든 단일 또는 다변량 다항식이 현대 알고리즘에 의해 인수될 수 있다는 사실은 이 문제가 지난 15년 동안 얼마나 성공적으로 공격되었는지를 보여준다. (에리히 칼토펜, 1982년)

오늘날, 현대의 알고리즘과 컴퓨터는 수천 자리 숫자의 계수를 가진 1000도 이상의 단변 다항식을 빠르게 고려할 수 있다.^[2] 이러한 목적을 위해, 합리적인 숫자와 숫자 필드를 고려하더라도, 기본적인 단계는 유한한 영역에 대한 다항식의 인자화다.

질문의 공식화

정수 또는 필드 위의 다항식 링은 고유한 요인화 도메인이다. 이는 이들 고리의 모든 원소가 상수의 산물이며 수정 불가능한 다항식(비정수 다항식 두 개의 산물이 아닌 다항식)의 산물이라는 것을 의미한다. 더욱이 이러한 분해는 변위 상수에 의한 인자의 곱셈까지 독특한 것이다.

인자화는 베이스 필드에 따라 달라진다. 예를 들어, 복잡한 계수를 가진 모든 다항식은 복잡한 뿌리를 가지고 있다고 기술하는 대수학의 기본 정리는 정수 계수를 가진 다항식을 복잡한 필드 C에 걸쳐 선형 인자로 인수할 수 있음을 암시한다. 이와 유사하게, 현실의 분야에 걸쳐서, 수정 불가능한 인자는 최대 2개의 학위를 가지고 있는 반면, 합리성 Q의 분야에 걸쳐 수정 불가능한 모든 수준의 다항식이 있다.

다항식 인자화 문제는 모든 요소가 컴퓨터에 표현될 수 있고 산술 연산을 위한 알고리즘이 있는 계산 가능한 분야의 계수에 대해서만 타당하다. 그러나 이는 충분하지 않은 조건이다. Fröhlich와 Shepherdson은 어떠한 인수 알고리즘도 존재할 수 없는 그러한 분야의 예를 제시한다.^[3]

인자화 알고리즘이 알려진 계수의 필드에는 프라임 필드(즉, 이성계 및 프라임 모듈식 산술의 필드)와 그것들의 정밀하게 생성된 필드 확장이 포함된다. 정수 계수도 추적 가능하다. Kronecker의 고전적 방법은 역사적 관점에서만 흥미롭다. 현대 알고리즘은 다음과 같은 일련의 과정을 거친다.

• 사각자유인자화
• 유한분야에 대한 인자화

및 감소:

• 다변량 사례에서 일변량 사례까지.
• 순수하게 초월 확장된 계수에서 지면 위에 있는 다변량 사례까지(아래 참조).
• 대수적 확장의 계수에서 지면장의 계수까지(아래 참조).
• 합리적인 계수에서 정수 계수까지(아래 참조).
• 잘 선택된 p(아래 참조)에 대한 정수 계수부터 p 요소가 있는 prime 필드의 계수까지.

원시 부품-함량 인자화

이 절에서는 Q(합리적 수)와 Z(정수)를 고려하는 것이 본질적으로 동일한 문제임을 보여 준다.

"cont(p)"로 표시된 다항식 p ∈ Z[X]의 내용은 부호까지 계수의 가장 큰 공통점이다. p의 원시 부분은 primpart(p)=p/cont(p)이며, 정수 계수를 갖는 원시 다항식이다. 이것은 p의 인자를 정수와 원시 다항식의 곱으로 정의한다. 이 요소화는 내용의 기호에 따라 독특하다. 원시 부분의 선행 계수가 양수인 것과 같은 내용의 기호를 선택하는 것이 통상적인 관례다.

예를 들어,

${\displaystyle -10x^{2}+5x+5=(-5)(2x^{2}-x-1)\,}$

콘텐츠와 원시적인 부분에 대한 요소화 입니다.

합리적인 계수를 가진 모든 다항식 q는 기록될 수 있다.

${\displaystyle q={\frac {p}{c},}$

여기서 p ∈ Z[X] 및 c ∈ Z: q의 계수(예: 제품)와 p = cq의 모든 분모 중 c를 곱하면 충분하다. q의 내용은 다음과 같이 정의된다.

${\displaystyle {\text{cont}(q)={\frac {{\text{cont}}{c},}$

그리고 q의 원시적인 부분은 p의 그것이다. 정수 계수를 갖는 다항식들에 대해서는, 이것은 합리적인 숫자로의 인자화와 정수 계수를 갖는 원시 다항식을 정의한다. 이 요소화는 또한 기호의 선택에 따라 독특하다.

예를 들어,

${\displaystyle {\frac{x^{5}}{3}+{7x^{2}}+2x^1={\frac {2x^{5}+21x^{2}+12x+6}{6}}}$

콘텐츠와 원시적인 부분에 대한 요소화 입니다.

가우스는 두 원시 다항식의 산물도 원시(가우스의 보조정리)라는 것을 증명했다. 이것은 원시 다항식이 정수에 걸쳐서 해석할 수 없는 경우에만 합리성에 대해 해석할 수 없다는 것을 암시한다. 이것은 또한 합리적인 계수를 갖는 다항식의 합리성에 대한 인자화가 원시 부분의 정수에 대한 인자화와 동일하다는 것을 암시한다. 마찬가지로 정수 계수를 갖는 다항식의 정수에 대한 인자화는 그 내용의 인자화에 의한 원시 부분의 인자화의 산물이다.

즉, 정수 GCD 계산은 이성보다 다항식의 인자화를 정수 계수를 갖는 원시 다항식의 인자화로, 정수와 원시 다항식의 인자화에 대한 인자화로 감소시킨다.

Z를 필드 F 위에 있는 다항식 링으로 대체하고 Q를 동일한 변수에서 F에 대한 합리적인 기능의 영역으로 대체하면 앞에 나오는 모든 것이 사실로 유지되며, "기호까지"라는 유일한 차이점은 "F에서 반전 가능한 상수에 의한 곱까지"로 대체해야 한다는 것이다. 이것은 F에 대한 다변량 다항식의 인자화까지 F의 순전히 초월적인 필드 확장에 대한 인자화를 감소시킨다.

사각자유인자화

만약 둘 이상의 다항식 요인이 동일하다면, 다항식은 이 인자의 제곱의 배수인 것이다. 또한 다중 인자는 다항식 파생상품의 한 요인이다(여러 변수일 경우 어떤 변수와도 관련).

일변량 다항식의 경우 다중 요인은 (적절한 확장 필드 위에) 다중 루트와 동일하다. 이성(또는 보다 일반적으로 특성 0의 영역에 걸친)을 초과하는 일변량 다항식의 경우, 윤의 알고리즘은 다항식을 정사각형이 없는 요인, 즉 정사각형의 배수가 아닌 인자로 효율적으로 인수하여 gcd(f(x), f(x)로 시작하는 GCD 연산 순서를 수행하기 위해 이를 이용한다. 초기 다항식을 고려하려면 각 제곱이 없는 요인을 고려하는 것으로 충분하다. 따라서 사각 자유 인자화는 대부분의 다항식 인자화 알고리즘의 첫 번째 단계다.

윤씨의 알고리즘은 다항 링 위에 있는 일항 다항 다항 다항식으로서 다항 다항식 다항식을 고려함으로써 이를 다항식 사례로 확장한다.

유한한 분야에 걸친 다항식의 경우, 그 특성보다 정도가 작은 경우에만 윤의 알고리즘이 적용된다. 그렇지 않으면 0이 아닌 다항식의 파생상품이 0일 수 있기 때문이다(p 요소가 있는 분야에서는 x의^p 다항식의 파생상품이 항상 0임). 그럼에도 불구하고, 다항식 및 그 파생상품으로부터 시작하는 GCD 연산은 제곱 없는 분해를 계산할 수 있게 한다. 유한한 필드에 대한 다항식 인자화#제곱 없는 인자화를 참조한다.

고전적 방법

이 절에서는 손으로 계산할 때 편리할 수 있는 교과서적인 방법을 설명한다. 이러한 방법은 현재 다항식 인자화보다 느린 정수 인자화를 사용하기 때문에 컴퓨터 연산에는 사용되지 않는다.

이어지는 두 가지 방법은 정수 계수가 있는 다항식 인자를 찾기 위한 정수 계수가 있는 일변량 다항식에서 시작한다.

선형 인자 획득

합리적인 계수를 가진 모든 선형 요인은 합리적인 뿌리 시험을 사용하여 찾을 수 있다. If the polynomial to be factored is ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$, then all possible linear factors are of the form ${\displaystyle b_{1}x-b_{0}}$, where ${\displaystyle b_{1}}$ is an integer factor o${\displaystyle f_{}}$ ${\$ 및 ${\displaystyle b_{}}$ $0{\displaystyle {}_{}}$ ${\$의 정수 인자는$$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$의 정수 인자로$,$ 가능한 모든 조합은 유효성을 시험할 수 있으며, 각 유효한 조합은 다항분할을 사용하여 인수할 수 있다. 원래 다항식이 2도 이상인 요인 중 최소 2개 이상의 인자의 산물인 경우, 이 기법은 부분 인자화만 제공할 뿐, 그렇지 않으면 인자화가 완료된다. 특히 비선형인자가 정확히 하나라면 모든 선형인자를 인자로 나눈 뒤 남은 다항식이 된다. 입방 다항식의 경우, 입방체가 전혀 인수 가능한 경우, 합리적 뿌리검사는 선형 인자와 불분명한 2차 인자로 또는 세 개의 선형 인자로 완전한 인자를 제공한다.

크로네커의 방법

크로네커의 방법은 정수 계수가 있는 일변량 다항식을 정수 계수가 있는 다항식에 인자화하는 것을 목적으로 한다.

이 방법은 정수 값으로 정수 다항식을 평가해야 정수가 생성된다는 사실을 사용한다. ${\displaystyle 즉}$, $f{\displaystyle }$( x${\displaystyle }$) ${\displaystyle f(x)}$이(가) 정수 계수를 가진 다항식인 경우, a가 정수인 ${\displaystyle \mathrm{즉시}}$f ( ${\displaystyle )}${\$displaystyle f(a)}$이 정수인 것이다. a 인자에 대해 가능한 정수 값의 수는 한정되어 있다. ${\displaystyle \mathrm{따라서}}$ $g{\displaystyle }$( x${\displaystyle }$) ${\displaystyle g(x)}$이(${\displaystyle 가}$) $f{\displaystyle }$( x${\displaystyle }$)${\displaystyle }$, ${\displaystyle f(x$)의 인수인 경우$,$ ${\displaystyle g}$(${\displaystyle }$) ${\displaystyle g(a)}$의 값은$$ ${\displaystyle f}$(${\displaystyle }$)${\displaystyle }$. ${\displaystyf(a$)의 인수 중 하나여야 한다$$$.$$}$

If one searches the factors of a given degree d, one can consider ${\displaystyle d+1}$ values, ${\displaystyle a_{0},\ldots ,a_{d}}$ for a, which give a finite number of possibilities for the tuple ${\displaystyle (f(a_{0}),\ldots ,f(a_{d}).$$}}$ 그러한$$ 각 튜플은 다항식 보간법으로 계산할 수 있는 기껏해야 d의 고유한 다항식을 정의하고 다항식 분할에 의한 인자임을 시험한다. 따라서 철저한 검색을 통해 모든 수준의 요인을 최대 d까지 찾을 수 있다.

예를 들어 다음을 고려하십시오.

${\displaystyle f}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {x\mathrm{}}^{}}$ 5${\displaystyle {}^{}}$+ ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}{}^{}}$+ ${\displaystyle {2\mathrm{}}^{}}$ +${\displaystyle {}^{}x}$ 2${\displaystyle }$+ ${\displaystyle 2}$ ${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2$ .

이 다항식 요인이 Z를 초과하는 경우 요인 $p{\displaystyle (}$ ${\displaystyle x}$) ${\displaystyle p(x)}$ 중 적어도 하나는 등급 2 이하가 되어야 하므로$$ $p{\displaystyle (x}$ )$${\$displaystyle$ p$(x)}$은 3개의 값으로 고유하게 결정된다. ${\displaystyle \mathrm{따라서}}$ 우리는 세 개의 값 $f{\displaystyle }$( 0${\displaystyle }$)${\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle$ f $(0)=2$ ${\displaystyle \mathrm{f}}$( ${\displaystyle 1}$)${\displaystyle }$= 6 ${\displaystyle$ f$(1)=6},$ $f$ (${\displaystyle }$- 1${\displaystyle }$)${\displaystyle }$= ${\displaystyle 2}$ ${\displaystyf(-1)=2}$을 계산한다$.$ 이들 값 중 하나가 0이면 선형 인자가 있다. 값이 0이 아닌 경우, 각 값에 대해 가능한 인자를 나열할 수 있다. 이제, 2는 오직 다음과 같이만 고려할 수 있다.

1×2, 2×1, (-1)×(-2), 또는 (-2)×(-1)×(1).

따라서 2도 정수 다항식 요인이 존재할 경우 값 중 하나를 취해야 한다.

p(0) = 1, 2, -1 또는 -2

그리고 p(1)도 마찬가지로. 6(1×6과 2×3)의 8가지 인자가 있어 총 4×4×8 = 128개의 가능한 3배수(p(0), p(1), p(-1)가 되며, 이 중 절반은 나머지 절반의 음으로 폐기할 수 있다. 따라서 우리는 $64개$의 명시적 정수 다항식 $p{\displaystyle }$ (${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle bx}$ + c $(\displaystyle p(x)=ax^{2}+$$bx$$+c}$를 f${\displaystyle }$($x)$의 가능한 인자로 확인해야$$ 한다$.$ 이들을 철저히 시험해 보면 다음과 같은 것이 드러난다.

${\displaystyle p(x)=x^{2}+x+1}$

(g(0), g(1), g11) = (1,3,1) $요인{\displaystyle }$ f${\displaystyle (x}$ ${\displaystyle )}$ ${\displaystyle$ f$(x$

Dividing f(x) by p(x) gives the other factor ${\displaystyle q(x)=x^{3}-x+2}$, so that ${\displaystyle f(x)=p(x)q(x)}$. Now one can test recursively to find factors of p(x) and q(x), in this case using the rational root test. 둘 다 수정할 수 없는 것으로 밝혀졌으므로 f(x)의 수정할 수 없는 요소화는 다음과 같다.^[4]

${\displaystyle f(x)=p(x)q(x^{2}+x+1)(x^{3}-x+2)}$

현대적 방법

유한분야 인수

정수에 대한 일변량 다항식 인수

$f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$이(가) 정수에 대한 일변량 다항식이고, 내용이 없고 사각형이 없는 것으로 가정된 경우, 어떤 $요인{\displaystyle }$ g${\displaystyle }$( ${\displaystyle x}$)$${\$displaystyle$ g$(x)$가 B ${\displaysty$ $B$에 의해 경계된 절대값의 계수를 갖도록$$$$ $바운드{\displaystyle }$ B${\dis$.$레이스타일 m}$은 2 ${\displaystyle B}$ ${\displaystyle 2B}$보다 큰 정수이며$,$ $g{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle g(x)}$이$($가) $modulo{\displaystyle }$ m ${\displaystyle m$$}$인 경우 g (${\displaystyle x}$) ${\displaystyle g$$(x)}$을(으) 이미지 $mod$에서 재구성할 수 있다$$$.$

자센하우스 알고리즘은 다음과 같이 진행한다. 먼저 $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle$ $f($$x$$)}$ 모드의$$ $이미지$가 사각형이 없고 $f$ ( x${\displaystyle }$) ${\displaystyle f(x)}$과 같은 수준으로 유지되도록$$ p {\$displaystyle$ $p}$을(를$)$ 선택한 다음 f${\displaystyle }$($) {\displaystystyle$ $}$을$($$으$$)$로 설정하십시오$.$ This produces integer polynomials ${\displaystyle f_{1}(x),...,f_{r}(x)}$ whose product matches ${\displaystyle f(x)}$ mod ${\displaystyle p}$. Next, apply Hensel lifting; this updates the ${\displaystyle f_{i}(x)}$ in such a way that their product matches ${\displaystyle f}$${\displaystyle (}$ ${\displaystyle x}$) ${\displaystyle$ $f$$(x)}$ mod$$ $a{\displaystyle {}^{}}$ $p {\displaystyle$ p$^{a$$}}$이(가) ${\displaystyle \mathrm{2B}}$ ${\displaystyle$ $p^{$$a}$를 초과할$$ 정도로 큰 $경우$$:$ 따라서 각 f ${\displaystyle i_{}}$ ${\displaystyle x}$) ${\displaysty f_{i}(x)$는 잘 정의된 정수 다항식에 해당한다$$. Modulo ${\displaystyle p^{a}}$, the polynomial ${\displaystyle f(x)}$ has ${\displaystyle 2^{r}}$ factors (up to units): the products of all subsets of ${\displaystyle {f_{1}(x),...,f_{r}(x)}}$ mod ${\displaystyle p^{a}}$. These factors modulo ${\displaystyle p^{a}}$ need not correspond to "true" factors of ${\displaystyle f(x)}$ in ${\displaystyle \mathbb {Z} [x]}$, but we can easily test them by division in ${\displaystyle \mathbb {Z} [x]}$. This way, all irreducible true factors can be found by checking 최대 ${\displaystyle {2r}^{}}$ ${\$ 케이스에서$$ 보완을 $건너뛰어{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {2r}^{}}$- ${\displaystyle 1^{}}$ ${\$ 2$^{r-1}$ 케이스로$$ 줄였다. $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$을(를) 축소할 수 있는 경우, 이미 발견된 참 인자에 나타나는$$ ${\displaystyle f_{}}$ (${\displaystyle {}_{}}$x${\displaystyle }$) ${\displaystyle f_{i}(x)}$을(를) 제거하여 사례 수를 더 줄인다. 자센하우스 알고리즘은 각각의 사례(각 부분집합)를 신속하게 처리하지만, 최악의 경우 기하급수적인 수의 경우를 고려한다.

이성적 다항식 인수를 위한 첫 번째 다항식 시간 알고리즘은 Lenstra, Lenstra, Lovasz에 의해 발견되었으며, Lenstra-Lenstra-Lovasz lattice basis recovery(LLL) 알고리즘(Lenstra, Lenstra & Lovasz 1982)의 적용이다. 다음과 같이와 정수 계수, wh은 로렌스 리버모어 연구소 인수 분해 알고리즘의 간편한 버전:()) 높은 정밀도에{\displaystyle f())}, 다항식 f의 복잡한(또는p-adic)뿌리 α를 계산한 다음 1일 사이에 개략적인 선형 관계, α, α2, α3을 찾기는 Lenstra–Lenstra–Lovász 격자 기초 감소 알고리즘을 사용합니다.이다ich는 $정확$한 선형 ${\displaystyle \mathrm{관계}}$와${\displaystyle }$f$$ x ) {\$displaystyle$f(x)}의 다항식 인자일 수 있다$.$ 이 방법이 인자를 생성하거나 또는 수정 불가능한 증거를 생성한다는 것을 보장하는 정밀도에 대한 경계를 결정할 수 있다. 이 방법은 다항식 시간에 마쳐지지만, 격자에는 치수가 높고 입력량이 커서 계산이 느리기 때문에 실제로는 사용하지 않는다.

The exponential complexity in the Zassenhaus algorithm comes from a combinatorial problem: how to select the right subsets of ${\displaystyle f_{1}(x),...,f_{r}(x)}$. State-of-the-art factoring implementations work in a manner similar to Zassenhaus, except that the combinatorial problem is translated to a LLL에 의해 해결되는 ^[5]격자 문제 이 접근법에서 LLL은 인자의 계수를 계산하는 데 ${\displaystyle {사용}_{}}$되지 않고, 오히려 f $1{\displaystyle {}_{}}$( ${\displaystyle x}$)${\displaystyle }$,${\displaystyle }$.${\displaystyle }$, ${\displaystyle f_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle x}$) ${\$ $displaystyle f_{1}(x$), $..., f_{r}(x)$의 하위 집합을 인코딩하는 {0,1}의 $r{\displaystyle }$ ${\displaystystyle r}$ 항목으로$$ 벡터를 계산하는 데 사용된다.

대수적 확장에 대한 인수(트래거의 방법)

다항식 $p{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle \in }$ ${\displaystyle K}$[ ${\displaystyle x}$ ${\displaystyle ]}$ ${\displaystyle p(x)\in K[x]}$을(를) 인수할 수 있다$.$ 여기서 필드 $K{\displaystyle }$ ${\displaystyle K}$은 Q ${\$의 유한 확장이다$.$ 먼저, 사각 자유 인수화를 사용하여 다항식이 제곱되지 않은 것으로 가정할 수 있다. Next we define the quotient ring ${\displaystyle L=K[x]/p(x)}$ of degree ${\displaystyle n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]}$; this is not a field unless ${\displaystyle p(x)}$ is irreducible, but it is a reduced ring since ${\di$$splaystyle p(x)}$은(는) 사각형이 없다. 과연

${\displaystyle p(x)=\prod _{i=1}^{m}p_{i}(x)}$

p(x)의 원하는 인수인자로, 링은 다음과 같이 고유하게 밭으로 분해된다.

${\displaystyle L=K[x]/p(x)\cong \prod _{i=1}^{m[x]/p_{i}(x).}$

우리는 인자를 모르는 사이에 이 부패를 찾아낼 것이다. 첫째로, $우리$는 Q ${\$에 대해 대수로 L을 명시적으로 쓴다$:$ 원시 요소 정리에 의해 높은 확률로$$ $Q{\displaystyle \mathbb{}}$ ${\$에 $걸쳐{\displaystyle }$ L ${\displaystystyle L}$을(를) 생성하는 임의 요소 $\alpha {\displaystyle }$ α ${\displaystyle \in }$ ${\displaystyle L}$ ${\displaypa \in$ L$}$을 선택한다. If this is the case, we can compute the minimal polynomial ${\displaystyle q(y)\in \mathbb {Q} [y]}$ of ${\displaystyle \alpha }$ over ${\displaystyle \mathbb {Q} }$, by finding a ${\displaystyle \mathbb {Q} }$-linear relation among 1, α, . . . , αⁿ. Using a factoring algorithm for rational poLyomials, $Q{\displaystyle \mathbb{}}$[ ${\displaystyle y}$ ${\displaystyle ]}$ ${\displaystyle \mathb {Q}$ [$y$ :

${\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y).}$

따라서 다음과 같은 이점을 얻을 수 있다.

${\displaystyle L\cong \mathb {Q} [y]/q(y)\cong \prod _{i=1}^{n}\mathb {Q}[y]/q_{i}(y),}$

여기서 $\alpha {\displaystyle }$ ${\displaystyle \alpha$}은$($는${\displaystyle )}$ $y{\displaystyle }$ 파운드${\displaystyle (}$y ${\displaystyle ,}$ ${\displaystyle y}$ ,${\displaystyle }$y ,${\displaystyle }$…${\displaystyle }$, ${\displaystyle y}$)$${\$displaystyle y\좌우타로우(y,$ y,$y,\ldots,y)}$에 해당한다$.$ 이것은 $L{\displaystyle }$ ${\displaystyle L}$의 이전 분해와 이형이어야 한다$.$

The generators of L are x along with the generators of ${\displaystyle K}$ over ${\displaystyle \mathbb {Q} }$; writing these as a polynomials in ${\displaystyle \alpha }$, we can determine the embeddings of ${\displaystyle x}$ and ${\displaystyle K}$ into each component ${\displaystyle \mathbb{Q}[y]/q_i(y)=K}$${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$. By finding the minimal polynomial of ${\displaystyle x}$ in ${\displaystyle \mathbb {Q} [y]/q_{i}(y)}$, we compute ${\displaystyle p_{i}(x)}$, and thus factor ${\displaystyle p(x)}$ over $$$K$

참고 항목

• 요소화 § 다항식, 기초적 경험적 방법 및 명시적 공식용

참고 문헌 목록

• Fröhlich, A.; Shepherson, J. C. (1955), "On the factorisation of polynomials in a finite number of steps", Mathematische Zeitschrift, 62 (1): 331–334, doi:10.1007/BF01180640, ISSN 0025-5874
• Trager, B.M. (1976), "Algebraic Factoring and Rational Function Integration", Proc. SYMSAC 76, Symsac '76: 219–226, doi:10.1145/800205.806338
• 버나드 Beauzamy, Enflo, 폴 왕(1994년 10월).Polynomials에 하나 또는 몇몇들을``양적 추정:.분석 및 이론의 상징성과 Massively 병렬 Computation"까지.수학 매거진. 67(4):243–257. doi:10.2307/2690843.JSTOR 2690843.{{ 들고 일기}}:CS1 maint:복수의 이름:작가들(링크)(대학 수학으로 독자들에게 접근할 수 있는)을 열거한다.
• Cohen, Henri (1993). A course in computational algebraic number theory. Graduate Texts in Mathematics. Vol. 138. Berlin, New York: Springer-Verlag. ISBN 978-3-540-55640-4. MR 1228206.
• Kaltofen, Erich (1982), "Factorization of polynomials", in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag, pp. 95–113, CiteSeerX 10.1.1.39.7916
• Knuth, Donald E (1997). "4.6.2 Factorization of Polynomials". Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 978-0-201-89684-8.
• Lenstra, A. K.; Lenstra, H. W.; Lovász, László (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. ISSN 0025-5831. MR 0682664.
• 반 데어 워든, 대수학(1970), 트랜스 블럼과 슐렌버거 프레데릭 언가르

추가 읽기

• Kaltofen, Erich (1990), "Polynomial Factorization 1982-1986", in D. V. Chudnovsky; R. D. Jenks (eds.), Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics, vol. 125, Marcel Dekker, Inc., CiteSeerX 10.1.1.68.7461
• Kaltofen, Erich (1992), "Polynomial Factorization 1987–1991" (PDF), Proceedings of Latin '92, Springer Lect. Notes Comput. Sci., vol. 583, Springer, retrieved October 14, 2012
• Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), "Schemes for Deterministic Polynomial Factoring", Proc. ISSAC 2009: 191–198, arXiv:0804.1974, doi:10.1145/1576702.1576730, ISBN 9781605586090