Factorization of polynomials

수학(mathematics) 및 컴퓨터 대수학(computer algebra)에서, 다항식의 인수분해(factorization of polynomials) 또는 다항식 인수분해(polynomial factorization)는 정수(integers) 또는 주어진 필드(field)에서 계수를 가진 다항식(polynomial)을 같은 도메인의 계수를 가진 기약 인수(irreducible factors)의 곱으로써 표현하는 과정입니다. 다항식 인수분해는 컴퓨터 대수학 시스템(computer algebra system)의 기본적인 도구 중 하나입니다.

첫 번째 다항식 인수분해 알고리듬은 1793년에 테오도르 폰 슈베르트(Theodor von Schubert)에 의해 출판되었습니다.^[1] 레오폴트 크로네커(Leopold Kronecker)는 1882년 슈베르트(Schubert)의 알고리듬을 재발견하고 다변수 다항식과 대수적 확대의 계수로 그것을 확장했습니다. 그러나, 이 주제에 관한 대부분의 지식은 1965년경 그리고 최초의 컴퓨터 대수학 시스템(computer algebra systems)보다 오래되지 않았습니다.

오랫동안 알려진 유한 단계 알고리듬이 처음 컴퓨터에 탑재되었을 때, 매우 비효율인 것으로 판명되었습니다. 적당한 크기의 계수 (100 비트에 이르기까지)를 가진 차수 거의 100까지의 임의의 일변수 또는 다변수 다항식은 컴퓨터 시간의 몇 분 안에 현대 알고리듬에 의해 인수분해될 수 있다는 사실은 이 문제가 지난 십오년 동안 얼마나 성공적으로 공격받았는지를 나타냅니다. (이엘커 켈투훈(Erich Kaltofen), 1982)

지금, 현대 알고리듬과 컴퓨터는 수천 자릿수의 계수를 갖는 1000보다 큰 차수의 일변수 다항식(univariate polynomials)을 빠르게 인수화할 수 있습니다.^[2]

Formulation of the question

정수 또는 필드에 걸쳐 다항식 링(Polynomial ring)은 고유한 인수분해 도메인(unique factorization domain)입니다. 이것은 이들 링의 모든 각 원소가 상수의 곱과 (두 개의 비-상수 다항식의 곱이 아닌) 기약 다항식(irreducible polynomial)의 곱이라는 것을 의미합니다. 게다가, 이 분해는 역수를 갖는 상수에 의한 인수들의 곱셈까지(up to) (즉, 곱셈을 제외하고) 유일합니다.

인수분해는 기본 필드에 따라 다릅니다. 예를 들어, 복소(complex) 계수를 갖는 모든 각 다항식이 복소수 근을 갖는다고 말하는, 대수학의 기본 정리(fundamental theorem of algebra)는 정수 계수를 갖는 다항식이 복소수 필드 C에 걸쳐 선형 인수(linear factor:일차 다항식)로 (근-찾기 알고리듬(root-finding algorithms)과 함께) 인수분해될 수 있음을 의미합니다. 비슷하게, 실수의 필드(field of reals)에 걸쳐, 기약 인수는 많아야 2차를 가지며, 반면에 유리수의 필드(field of rationals) Q에 걸쳐 기약이 되는 임의의 차수의 다항식이 있습니다.

다항식 인수분해의 질문은 모든 각 원소가 컴퓨터에서 표현될 수 있는 계산 가능 필드(computable field)의 계수, 그리고 그것들에 대해 산술 연산에 대한 알고리듬이 있는 것에 오직 의미를 가집니다. 프뢸리히(Fröhlich)와 쉐파슨(Shepherson)은 인수분해 알고리듬이 존재하지 않는 필드의 예제를 제공했습니다.

인수분해 알고리듬이 알려져 있는 계수의 필드는 소수 필드 (즉, 유리수의 필드(field of rationals) 그리고 소수 모듈러 산술(modular arithmetic)) 그리고 유한하게 생성된 필드 확장(finitely generated field extension)을 포함합니다. 정수 계수는 역시 다루기 쉽습니다. 크로네커의 고전적 방법은 역사적인 관점에서 오직 흥미롭습니다; 현대 알고리듬은 다음의 계승

제곱-없는 인수분해
유한한 필드에 걸쳐 인수분해

그리고 다음의 감소에 의해 진행되고 있습니다:

다변수(multivariate) 경우로부터 일변수(univariate) 경우로.
순수 초월 확장(purely transcendental extension) 계수로부터 기본 필드에 걸쳐 다변수의 경우로 (아래를 참조하십시오).
대수적 확장에서 계수로부터 기본 필드에서 계수로 (아래를 참조하십시오).
유리수 계수로부터 정수 계수로 (아래를 참조하십시오).
정수 계수에서, 잘 선택된 p에 대해, p 원소를 갖는 소수 필드에서 계수로 (아래를 참조하십시오).

Primitive part–content factorization

이 절에서, (유리수) Q에 걸쳐 그리고 (정수) Z에 걸친 인수화는 본질적으로 같은 문제라는 것을 보여줍니다.

"cont(p)"로 나타내는, 다항식 p ∈ Z[X]의 컨텐트(content)는, 그의 부호까지(up to) (즉, 부호를 제외하고), 그의 계수의 최대공약수(greatest common divisor)입니다. p의 원시 부분(primitive part)은 primpart(p)=p/cont(p)이며, 정수 계수를 가진 원시 다항식(primitive polynomial)입니다. 이것은 p의 인수분해를 정수와 원시 다항식의 곱으로 정의합니다. 이 인수분해는 컨텐트의 부호까지 (즉, 부호를 제외하고) 고유합니다. 원시 부분의 선행 계수가 양수를 만족하는 컨텐트의 부호를 선택하는 것이 보통 관례입니다.

예를 들어,

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

은 컨텐트와 원시 부분으로의 인수분해입니다.

유리수 계수를 갖는 모든 각 다항식 q는 다음으로 쓸 수 있습니다:

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

여기서 p ∈ Z[X] 그리고 c ∈ Z입니다: 그것은 c에 대해 (예를 들어 그들의 곱) q의 계수의 모든 분모의 배수와 p = cq를 취하는 것으로 충분합니다. q의 컨텐트는 다음으로 정의됩니다:

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

그리고 q의 원시 부분은 p의 그것입니다. 정수 계수를 가진 다항식에 대해, 이것은 유리수와 정수 계수를 갖는 다항식으로의 인수분해를 정의합니다. 이 인수분해는 역시 부호의 선택까지 (선태을 제외하고) 고유합니다.

예를 들어,

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

은 컨텐트와 원시 부분으로 인수분해입니다.

가우스(Gauss)는 두 개의 원시 다항식의 곱이 역시 원시라는 것을 증명했습니다 (가우스의 보조정리(Gauss's lemma)). 이것은 원시 다항식이 유리수에 걸쳐 기약인 것과 그것이 정수에 걸쳐 기약인 것은 필요충분 조건이라는 것을 의미합니다. 이것은 유리수 계수를 가진 다항식의 유리수에 걸쳐 인수분해가 그의 원시 부분의 정수에 걸쳐 인수분해와 동일하다는 것을 역시 의미합니다. 비슷하게, 정수 계수를 가진 다항식의 정수에 걸쳐 인수분해는 그의 컨텐트의 인수분해에 의한 그의 원시 부분의 인수분해의 곱입니다.

다시 말하면, 정수 GCD 계산은 유리수에 걸쳐 다항식의 인수분해를 정수 계수를 가진 원시 다항식의 인수분해로 감소시키고, 정수에 걸쳐 인수분해를 정수와 원시 다항식의 인수분해로 감소시킵니다.

앞의 모든 각 내용은, 만약 Z가 필드 F에 걸쳐 다항식 링으로 대체되고 Q가 같은 변수에서 F에 걸쳐 유리 함수의 필드(field of rational functions)로 대체되면, 참으로 남습니다. 오직 차이점은 "부호까지"는 "F 안의 역이 존재하는 상수에 의한 곱셈까지"로 반드시 대체되어야 합니다. 이것은 F의 순수 초월(purely transcendental) 필드 확장에 걸쳐 인수분해를 F에 걸쳐 다변수 다항식(multivariate polynomial)의 인수분해로 감소시킵니다.

Square-free factorization

만약 다항식의 둘 이상의 인수가 서로 동일하면, 다항식은 이 인수의 제곱의 중복입니다. 일변수 다항식의 경우에서, 이것은 중복 근(multiple roots)을 생성합니다. 이 경우에서, 그런 다음 중복 인수는 역시 다항식의 (만약 여럿이면, 변수의 임의의 것에 관한) 도함수(derivative)의 인수입니다. 유리수에 걸쳐 (또는 보다 일반적으로 특성(characteristic) 영의 필드에 걸쳐) 일변수 다항식의 경우에서, 윤의 알고리듬(Yun's algorithm)은 이것을 다항식을 제곱없는 인수, 즉 제곱의 중복이 아닌 인수로 효율적으로 인수화하기 위해 개발합니다. 초기 다항식을 인수화하기 위해, 각 제곱-없는 인수를 인수화하는 것으로 충분합니다. 제곱-없는 인수분해는 따라서 대부분의 다항식 인수분해 알고리듬의 첫 번째 단계입니다.

윤의 알고리듬은 이것을 다변수 다항식을 다변수 링에 걸쳐 일변수 다항식으로 고려함으로써 다변수 경우에 대해 확장합니다.

유한한 필드에 걸쳐 다항식의 경우에서, 윤의 알고리듬은 차수가 특성보다 작은 경우에만 적용되는데, 왜냐하면, 그렇지 않으면, 비-영 다항식의 도함수는 영일 수 있기 때문입니다 (p 원소를 갖는 필드에 걸쳐, x^p에서 다항식의 도함수는 항상 영입니다). 그럼에도 불구하고, 다항식과 그의 도함수로부터 시작하는, 일련의 GCD 계산은 제곱-없는 분해를 계산하는 것을 허용합니다; 제곱-없는 인수분해를 참조하십시오.

Classical methods

이 절은 손으로 계산할 때 편리할 수 있는 교과서 방법을 설명합니다. 이들 방법은 정수 소인수분해(integer factorization)를 사용하기 때문에 컴퓨터 계산에 사용되지 않으며, 현재까지 다항식 인수분해보다 훨씬 더 느립니다.

Obtaining linear factors

유리수 계수를 가진 모든 선형 인수는 유리수 근 테스트(rational root test)를 사용하여 찾아질 수 있습니다. 만약 인수화할 다항식이 $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}$ 이면, 모든 가능한 선형 인수는 형태 $b_{1}x-b_{0}$ 이고, 여기서 $b_{1}$ 은 $a_{n}$ 의 정수 인수이고 $b_{0}$ 은 $a_{0}$ 의 정수 인수입니다. 정수 인수의 모든 가능한 조합은 유효성에 대해 테스트될 수 있고, 각 유효한 인수는 다항식 긴 나눗셈(polynomial long division)을 사용하여 인수화될 수 있습니다. 만약 원래 다항식이 차수 2 이상의 적어도 두 개 이상의 인수의 곱이면 이 기법은 부분 인수분해를 오직 제공합니다; 그렇지 않으면 인수분해가 완전한 것입니다. 특히, 만약 정확히 하나의 비-선형 인수가 있으면, 모든 선형 인수가 인수분해된 후 남은 다항식일 것입니다. 삼차 다항식(cubic polynomial)의 경우에서, 만약 삼차가 적어도 인수분해 가능하면, 유리 근 테스트는 선형 인수와 기약 이차 인수 또는 세 개의 선형 인수로 완전한 인수분해를 제공합니다.

Kronecker's method

정수 다항식은 반드시 정수 다항식으로 인수화되고, 정수 값에서 정수 다항식을 평가하는 것은 반드시 정수를 생성하고, 다항식의 정수 값은 오직 방법의 유한한 숫자로 인수화될 수 있고, 오직 가능한 다항식 인수의 유한한 숫자로 생성될 수 있습니다.

예를 들어, 다음을 생각해 보십시오:

f(x)=x^{5}+x^{4}+x^{2}+x+2

.

만약 이 다항식이 Z에 걸쳐 인수분해하면, 그의 인수의 적어도 하나는 반드시 차수 2이하여야 합니다. 우리는 이차 다항식에 유일하게 적합한 세 개의 값이 필요합니다. 우리는 $f(0)=2$ , $f(1)=6$ 및 $f(-1)=2$ 을 사용할 것입니다. 만약 그 값들의 하나가 0이라면, 우리는 이미 근 (그리고 그래서 인수)을 찾았습니다. 만약 영인 것이 없으면, 각각은 약수의 유한한 숫자를 가집니다. 이제, 2는 다음으로 오직 소인수분해할 것입니다:

1×2, 2×1, (−1)×(−2), or (−2)×(−1).

그러므로, 만약 이차 정수 다항식 인수가 존재하면, 그것은 $x=0$ 에서, 마찬가지로 $x=-1$ 에서, 다음 값의 하나를 취해야 합니다:

1, 2, −1, or −2

인수 6에 대한 여덟 개의 다른 방법 (6의 각 약수에 대해 하나)이 있으므로, 그래서 다음의

4×4×8 = 128

가능한 조합이 있고, 이들의 절반은 다른 절반의 음의 것이기 때문에 버려질 수 있으므로, 반드시 검사되어야 하는 64 개의 가능한 이차 정수 다항식에 대응합니다. 이것들은 오직 $f(x)$ 의 가능한 정수 다항식 인수입니다. 그들을 철저히 테스트함으로써,

p(x)=x^{2}+x+1

가 $p(0)=1$ , $p(1)=3$ 및 $p(-1)=1$ 으로부터 구성되고, 인수 $f(x)$ 를 구성되는 것이 드러납니다.

$p$ 에 의해 $f$ 를 나누는 것은 다른 인수 $q(x)=x^{3}-x+2$ 를 제공하므로, $f=pq$ 입니다. 이제 $p$ 와 $q$ 의 인수를 찾기 위해 재귀적으로 테스트할 수 있습니다. 그들 모두는 정수에 걸쳐 기약인 것으로 밝혀지므로, $f$ 의 기약 인수분해는 다음과 같습니다:^[3]

f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2).

Modern methods

Factoring over finite fields

Factoring univariate polynomials over the integers

만약 $f(x)$ 가 정수에 걸쳐 일변수 다항식이고, 컨텐트-없는(content-free) 및 제곱-없는(square-free) 것으로 가정되면, 임의의 인수 $g(x)$ 는 $B$ 에 의해 경계진 절대 값의 계수를 가지는 것을 만족하는 경계 $B$ 를 계산하는 것으로 시작합니다. 이 방식으로, 만약 $m$ 이 $2B$ 보다 큰 정수이고, 만약 $g(x)$ 가 모듈러 $m$ 으로 알려져 있으면, $g(x)$ 는 그의 이미지 모드 $m$ 에서 재구성될 수 있습니다.

차센하우스(Zassenhaus) 알고리듬은 다음으로 진행됩니다. 먼저, $f(x)$ 모드 $p$ 의 이미지가 제곱-없는(square-free), $f(x)$ 와 같은 차수로 남겨지는 것을 만족하는 소수 $p$ 를 선택하십시오. 그런 다음 인수 $f(x)$ 모드 $p$ 입니다. 이것은 그들 곱이 $f(x)$ 모드 $p$ 와 일치하는 정수 다항식 $f_{1}(x),...,f_{r}(x)$ 을 생성합니다. 다음으로, 헨젤 리프팅(Hensel lifting)을 적용하면, 이것은, 이제 그들 곱은 $f(x)$ 모드 $p^{a}$ 와 일치하는, 그러한 방식으로 $f_{i}(x)$ 를 업데이트하며, 여기서 $a$ 는, $p^{a}$ 는 $2B$ 보다 큰 그러한 방식으로 선택됩니다. 모듈러 $p^{a}$ , 다항식 $f(x)$ 는 (단위까지) $2^{r}$ 인수를 가집니다: ${f_{1}(x),...,f_{r}(x)}$ 의 각 부분집합에 대해, 곱은 $f(x)$ 모드 $p^{a}$ 의 인수입니다. 어쨌든, 인수 모듈로 $p^{a}$ 는 소위 "참 인수"("true factor"): $Z[x]$ 안의 $f(x)$ 의 인수에 해당할 필요는 없습니다. 각 인수 모드 $p^{a}$ 에 대해, 우리는 만약 그것이 "참" 인수에 해당하는지 테스트할 수 있고, 그리고 만약 그렇다면, $p^{a}$ 가 $2B$ 를 넘는 것에서 제공되는 "참" 인수를 찾을 수 있습니다. 이 방법으로, 모든 기약 "참" 인수는 최대 $2^{r}$ 경우를 검사함으로써 찾아질 수 있습니다. 이것은 여(complement)를 무시함으로써 $2^{r-1}$ 경우로 축소됩니다. 만약 $f(x)$ 가 비-기약이면, 경우의 숫자는 이미 발견된 "참" 인수에 나타나는 그들 $f_{i}(x)$ 를 제거함으로써 더 줄어듭니다. 차센하우스 알고리듬은 각 경우 (각 부분집합)를 빠르게 처리하고, 어쨌든, 최악의 경우에서, 그것은 경우의 지수적 숫자를 고려합니다.

유리수 다항식을 인수화하는 것에 대해 첫 번째 다항식 시간(polynomial time) 알고리듬은 렌스트라, 렌스트르 및 로바스에 의해 발견되었고, 렌스트라–렌스트라–로바스 격자 기반 축소 알고리듬(Lenstra–Lenstra–Lovász lattice basis reduction algorithm), "LLL 알고리듬"의 응용입니다. (Lenstra, Lenstra & Lovász 1982) LLL 인수분해 알고리듬의 단순화된 버전은 다음과 같습니다: 다항식 $f(x)$ 의 복소수 (또는 p-진수) 근 α을 고정밀도로 계산하고, 그런 다음 렌스트라–렌스트라–로바스 격자 기반 축소 알고리듬을 사용하여, 정수 계수를 갖는 1, α, α², α³, ... 사이의 근사 선형 관계를 찾는데, 이것은 정확한 선형 관계 그리고 $f(x)$ 의 다항식 인수가 될 수 있습니다. 이 방법은 인수, 또는 기약성 증명을 생성하는 것을 보장하는 정밀도에 대해 경계를 결정할 수 있습니다. 비록 이 방법이 다항식 시간일지라도, 그것은 실제로 사용되지 않았는데 왜냐하면 격자는 높은 차원 그리고 거대한 엔트리를 가지며, 이것은 계산을 느리게 만들기 때문입니다.

차센하우스 알고리듬에서 지수적 복잡도는 조합 문제: $f_{1}(x),...,f_{r}(x)$ 의 올바른 부분집합을 선택하는 방법에서 비롯됩니다. 최첨단 인수화의 구현은 조합 문제가 LLL에 의해 해결되는 격자 문제로 변환된다는 점을 제외하고는 차센하우스와 방식에서 유사하게 작동합니다.^[4] 이 접근법에서, LLL은 인수의 계수를 계산하는 데 사용되지 않고, 대신에, 그것은 기약 "참" 인수에 해당하는 $f_{1}(x),...,f_{r}(x)$ 의 부분집합을 인코딩하는 {0,1}의 $r$ 엔트리를 갖는 벡터를 계산하기 위해 사용됩니다.

Factoring over algebraic extensions (Trager's method)

우리는 다항식 $p(x)\in K[x]$ 을 인수화할 수 있고, 여기서 필드 $K$ 는 $\mathbb {Q}$ 의 유한한 확장입니다. 먼저, 제곱-없는 인수분해(square-free factorization)를 사용하여, 다항식이 제곱-없는 것으로 가정할 것입니다. 다음으로 $L=K[x]/p(x)$ 를 $\mathbb {Q}$ 에 걸쳐 대수로 명시적으로 씁니다. 다음으로 확률 원소 $\alpha \in L$ 를 선택합니다. 원시 원소 정리에 의해, $\alpha$ 는 높은 확률을 갖는 $\mathbb {Q}$ 에 걸쳐 $L$ 을 생성합니다. 만약 이것이 그 경우이면, $\mathbb {Q}$ 에 걸쳐 $\alpha$ 의 최소 다항식 $q(y)\in \mathbb {Q} [y]$ 를 계산할 수 있습니다. $\mathbb {Q} [y]$ 에 걸쳐 다음과 같이 인수화하는 것은,

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

다음을 결정합니다:

L=\mathbb {Q} [\alpha ]=\mathbb {Q} [y]/q(y)=\prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y)

( $L$ 은 축소된 링(reduced ring)으로, 왜냐하면 $p(x)$ 는 제곱-없는 것이기 때문임에 주의하십시오), 여기서 $\alpha$ 는 원소 $(y,y,\ldots ,y)$ 에 해당합니다. 이것은 필드의 곱으로 $L$ 의 고유한 분해인 것에 주목하십시오. 그러므로 이 분해는 다음과 같습니다:

\prod _{i=1}^{m}K[x]/p_{i}(x)

여기서

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

은 $K[x]$ 에 걸쳐 $p(x)$ 의 인수분해입니다. $\alpha$ 에서 $x\in L$ 와 와 $K$ 의 생성자를 다항식으로 쓰는 것에 의해, 구성요소 $\mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)$ 에 $x$ 와 $K$ 의 삽입을 결정할 수 있습니다. 이 링에서 $x$ 의 최소 다항식을 찾는 것에 의해, $p_{i}(x)$ 를 계산하고, 따라서 $K$ 에 걸쳐 $p(x)$ 를 인수화합니다.

Bibliography

^ FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)
^ An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, p. 163-170 (2011).
^ Van der Waerden, Sections 5.4 and 5.6
^ M. van Hoeij: Factoring polynomials and the knapsack problem. Journal of Number Theory, 95, 167-189, (2002).

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., "Algebraic Factoring and Rational Function Integration", Proc. SYMSAC 76
Bernard Beauzamy, Per Enflo, Paul Wang (October 1994). "Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation". Mathematics Magazine. 67 (4): 243–257. doi:10.2307/2690843. JSTOR 2690843. {{cite journal}}: Invalid |ref=harv (help)CS1 maint: multiple names: authors list (link) (accessible to readers with undergraduate mathematics)
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. {{cite book}}: Invalid |ref=harv (help)
Kaltofen, Erich (1982), "Factorization of polynomials", in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag, 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 0-201-89684-2.
Lenstra, A. K.; Lenstra, H. W.; Lovász, László (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. doi:10.1007/BF01457454. ISSN 0025-5831. MR 0682664. {{cite journal}}: Invalid |ref=harv (help)
Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.