Polynomial greatest common divisor

대수학(algebra)에서, 두 다항식(polynomial)의 최대 공통 약수(greatest common divisor) (자주 GCD로 약칭됨)는 가장 높은 가능한 차수의 다항식이며, 즉 두 원래 다항식 둘 다의 인수(factor)입니다. 이 개념은 두 정수의 최대 공통 약수(greatest common divisor)와 유사합니다.

필드(field)에 걸쳐 일변수(univariate) 다항식의 중요한 경우에서, 다항식 GCD는, 정수 GCD와 마찬가지로, 긴 나눗셈(long division)을 사용하는 유클리드의 알고리듬(Euclid's algorithm)에 의해 계산될 수 있습니다. 다항식 GCD는 역-가능한 상수에 의한 오직 곱셈까지(up to) 정의됩니다.

정수 GCD와 다항식 GCD 사이의 유사성은 유클리드의 알고리듬과 유클리드 나눗셈(Euclidean division)으로부터 추론될 수 있는 모든 속성을 일변수 다항식으로 확장하는 것을 허용합니다. 게다가, 다항식 GCD는 대수학의 다양한 영역에서 기본적인 개념을 만드는 특정 속성을 가집니다. 전형적으로, 두 다항식의 GCD의 근(root)은 두 개의 다항식의 공통 근이고, 이것은 그들을 계산하는 것없이 근에 대한 정보를 얻는 것을 허용합니다. 예를 들어, 다항식의 중복 근(multiple root)은 다항식과 그의 도함수의 GCD의 근이고, 더 나아가서 GCD 계산은 다항식의 제곱-없는 인수분해(square-free factorization)를 계산하는 것을 허용하며, 이것은 그의 근이 주어진 중복도(multiplicity)의 근인 다항식을 제공합니다.

최대 공통 약수는, 보다 일반적으로, 필드 또는 정수의 링, 및 역시 고유한 인수분해 도메인(unique factorization domain)에 걸쳐 다변수 다항식(multivariate polynomial)에 대해 정의되고 존재할 수 있습니다. 계수의 링에서 GCD 알고리듬을 가지는 순간 그들을 계산하기 위한 알고리듬이 존재합니다. 이들 알고리듬은 유클리드의 알고리듬의 변형으로 문제를 줄이기 위해 변수의 숫자에 대한 재귀(recursion)에 의해 진행됩니다. 그들은 컴퓨터 대수학(computer algebra)에서 기본 도구인데, 왜냐하면 컴퓨터 대수 시스템(computer algebra system)은 파편을 단순화하기 위해 체계적으로 그들을 사용하기 때문입니다. 반대로, 다항식 GCD의 현대 이론의 대부분은 컴퓨터 대수 시스템의 효율성의 요구를 충족시키기 위해 개발되어 왔습니다.

General definition

p와 q를 정수 도메인(integral domain) F, 전형적으로 필드(field) 또는 정수에서 계수(coefficients)를 갖는 다항식으로 놓습니다. p와 q의 최대 공통 약수는 p와 q를 나누고 p와 q의 모든 각 공통 약수가 역시 d를 나누는 것을 만족하는 다항식 d입니다. (둘 다 영이 아닌) 다항식의 모든 각 쌍이 GCD를 가지는 것과 F가 고유한 인수-분해 도메인(unique factorization domain)인 것은 필요충분 조건입니다.

만약 F가 필드이고 p와 q가 둘 다 영이 아니면, 최대 공통 약수가 되는 d에 대해 p와 q를 둘 다 나누는 것으로 충분하고 이 속성을 가지는 다항식 중에서 가장 큰 차수를 가집니다. 만약 p = q = 0이면, GCD는 0입니다. 어쨌든, 일부 저자는 GCD가 이 경우에서 정의되지 않은 것으로 여깁니다.

p와 q의 최대 공통 약수는 보통 "gcd(p, q)"로 나태냅니다.

최대 공통 약수는 고유하지 않습니다: 만약 d가 p와 q의 GCD이면, 다항식 f가 또 다른 GCD인 것과 다음을 만족하는 F의 역-가능한 원소 u가 있는 것은 필요충분 조건입니다:

f=ud

및

d=u^{-1}f

.

달리 말해서, GCD는 역-가능한 상수에 의해 곱셈까지(up to) 고유합니다.

정수의 경우에서, 이 불확정은, GCD로, 양수인 고유한 것을 선택함으로써 정해져 왔습니다 (또 다른 하나가 있으며, 이것은 그것의 반대 숫자입니다). 이 관례와 함께, 두 정수의 GCD는 역시 (보통 순서화에 대해) 최대 공통 약수입니다. 어쨌든, 정수 도메이에 걸쳐 다항식에 대해 자연스러운 전체 순서(total order)가 없기 때문에, 우리는 여기서 같은 방법으로 진행할 수 없습니다. 필드에 걸쳐 일변수(univariate) 다항식에 대해, 우리는 GCD가 일계수(monic)가 되도록 요구할 수 있지만 (즉, 그것은 최고 차수의 계수로 1을 가집니다), 보다 일반적인 경우에서 일반적인 관례가 없습니다. 그러므로, d = gcd(p, q) 또는 gcd(p, q) = gcd(r, s)와 같은 상등은 보통 표기법의 남용이며 이것은 "d는 p와 q의 GCD입니다" 및 "p, q는 r, s와 GCD의 같은 집합을 가집니다"로 읽혀야 합니다. 특히, gcd(p, q) = 1은 역-가능한 상수가 오직 공통 약수이고, 따라서 p와 q는 서로소(coprime)임을 의미합니다.

Properties

위에서 언급된 것처럼, 두 다항식의 GCD는 계수가 필드, 정수의 링 또는 보다 일반적으로 고유한 인수-분해 도메인(unique factorization domain)에 속하면, 존재합니다.
만약 c가 p와 q의 임의의 공통 약수이면, c는 그들의 GCD를 나눕니다.
$\gcd(p,q)=\gcd(q,p).$
임의의 다항식 r에 대해 $\gcd(p,q)=\gcd(q,p+rq)$ . 이 속성은 유클리드 알고리듬의 증명의 기초게 있습니다.
계수의 링의 역-가능한 원소 k에 대해, $\gcd(p,q)=\gcd(p,kq)$ .
따라서, $a_{1}b_{2}-a_{2}b_{1}$ 이 역-가능한 것을 만족하는 임의의 스칼라 $a_{1},b_{1},a_{2},b_{2}$ 에 대해 $\gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)$ 입니다.
만약 $\gcd(p,r)=1$ 이면, $\gcd(p,q)=\gcd(p,qr)$ 입니다.
만약 $\gcd(q,r)=1$ 이면, $\gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)$ 입니다.
필드에 걸쳐 두 일변수 다항식 p와 q에 대해, $\gcd(p,q)=ap+bq$ 와 $\gcd(p,q)$ 가 p와 q의 모든 각 그러한 선형 조합을 나누는 것 (베주의 항등식(Bézout's identity))을 만족하는 다항식 a와 b가 존재합니다.
셋 이상의 다항식의 최대 공통 약수는 두 다항식에 대한 것에서 처럼 비슷하게 정의될 수 있습니다. 다음 항등식에 의해 두 다항식의 GCD로부터 재귀적으로 계산될 수 있습니다:

\gcd(p,q,r)=\gcd(p,\gcd(q,r)),

및

\gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).

GCD by hand computation

두 다항식의 최대 공통 약수를 구하는 여러 방법이 있습니다. 그들 중 둘은 다음입니다:

다항식의 인수-분해(Factorization of polynomials), 이것에서 우리는 각 표현의 인수를 찾고, 그런-다음 각 인수 집합 이내로부터 모두에 의해 보유된 공통 인수의 집합을 선택합니다. 이 방법은 간단한 경우에서 오직 유용할 수 있는데, 왜냐하면 인수화는 보통 최대 공통 약수를 계산하는 것보다 훨씬 어렵기 때문입니다.
유클리드 알고리듬(Euclidean algorithm), 이것은 두 숫자에 대해서 처럼, 같은 방법에서 두 다항식의 GCD를 찾기 위해 사용될 수 있습니다.

Factoring

인수화를 사용하여 두 다항식의 GCD를 찾기 위해, 단순히 두 다항식을 완전히 인수화하십시오. 그런-다음 모든 공통 인수를 곱하십시오. 이 단계에서, 우리는 일계수 다항식을 반드시 가질 필요는 없으므로, 마지막으로 이것을 일계수 다항식으로 만들기 위해 상수를 곱하십시오. 이것은 두 다항식의 GCD가 될 것인데, 왜냐하면 그것은 모든 공통 약수를 포함하고 일계수이기 때문입니다.

예제 일: $x 2 + 7 x + 6$ 및 $x 2 - 5 x - 6$ 의 GCD를 구하십시오.

x 2 + 7 x + 6 = (x + 1)(x + 6)

x 2 - 5 x - 6 = (x + 1)(x - 6)

따라서, 그들의 GCD는 $x + 1$ 입니다.

Euclidean algorithm

다항식을 인수화하는 것은, 특히 만약 다항식이 큰 차수를 가지면, 어려울 수 있습니다. 유클리드 알고리듬(Euclidean algorithm)은 다항식의 임의의 쌍에 대해 작동하는 방법입니다. 그것은 유클리드 나눗셈(Euclidean division)의 반복적 사용을 만듭니다. 이 알고리듬을 두 숫자에 사용할 때, 숫자의 크기는 각 단계에서 감소합니다. 다항식과 함께, 다항식의 차수가 각 단계에서 감소합니다. 마지막 비-영 나머지가, 필요하다면 일계수로 만들며, 두 다항식의 GCD입니다.

보다 구체적으로, 우리는 두 다항식 $a (x)$ 및 $b (x)$ 의 gcd를 구하기를 원하며, 여기서 우리는 다음을 가정할 수 있습니다:

\deg(b(x))\leq \deg(a(x))\,.

우리는 다음을 만족시키는 두 다항식 $q (x)$ 및 $r (x)$ 을 찾을 수 있습니다 (다항식 긴 나눗셈(Polynomial long division)을 참조하십시오)

$a(x)=q_{0}(x)b(x)+r_{0}(x)$
$\deg(r_{0}(x))<\deg(b(x))$

다항식 $q 0 (x)$ 는 몫으로 불리고 $r 0 (x)$ 는 나머지입니다. 다항식 $g (x)$ 가 $a (x)$ 와 $b (x)$ 를 나누는 것과 그것이 $b (x)$ 와 $r 0 (x)$ 를 나누는 것은 필요충분 조건임을 주목하십시오. 우리는 다음을 추론합니다:

\gcd(a(x),b(x))=\gcd(b(x),r_{0}(x))\,.

그런-다음 다음을 놓습니다:

a_{1}(x)=b(x),b_{1}(x)=r_{0}(x)\,.

새로운 다항식 $q 1 (x), r 1 (x), a 2 (x), b 2 (x)$ 을 얻기 위해 다항식 긴 나눗셈(polynomial long division)을 반복하고, 이것을 계속하십시오. 각 단계에서 우리는 다음을 가집니다:

\deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k})\ ,

그래서 수열은 결국 다음에서 한 점에 이를 것이고

b_{N}(x)=0

우리는 GCD를 구할 것입니다:

\gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}\,.

예제: $x 2 + 7 x + 6$ 및 $x 2 - 5 x - 6$ 의 GCD를 구하시오.

x 2 + 7 x + 6 = (x 2 - 5 x - 6) (1) + (x + 1) (12)

x 2 - 5 x - 6 = (x + 1) (x - 6) + 0

$x + 1$ 가 마지막 비-영 나머지이므로, 이들 다항식의 GCD는 $x + 1$ 입니다.

이 방법은 만약 우리가 계수의 필드 원소의 영에 대한 상등을 테스트할 수 있으면 오직 작동하므로, 우리는 생성자와 관계가 정확하게 알려져 있는, 일부 유한하게 생성된 필드의 원소로서 계수의 설명을 요구합니다. 만약 계수가 오직 근사적으로 알려진 부동-소수점 숫자이면, 우리는 보통 SVD를 기반으로 완전히 다른 기법을 사용합니다.

이것은 새로운 어려움을 야기합니다: 유한 필드를 제외한 모든 이들 필드에 대해, 계수는 분수입니다. 만약 분수가 계산동안 단순화되지 않으면, 계수의 크기가 계산동안 지수적으로 증가하며, 이것은 매우 작은 차수를 제외하고 그것을 불가능하게 만듭니다. 다른 한편으로, 분수를 즉시 단순화하기 위해 소비하는 시간이 많습니다. 그러므로, 두 가지 다른 대안적인 방법이 도입되어 왔습니다 (아래를 참조하십시오):

유사-나머지 수열, 특히 부분-결과식 수열
모듈러 산술(modular arithmetic)을 사용하는 모듈러 GCD 알고리듬

Univariate polynomials with coefficients in a field

필드에 걸쳐 일변수 다항식의 경우는 여러 이유로 특히 중요합니다. 첫째, 그것은 가장 기본적인 경우이고 따라서 대수학의 대부분의 첫 번째 과정에 나타납니다. 둘째, 그것은 정수의 경우와 매우 유사하고, 이 아날로그는 유클리드 도메인(Euclidean domain)의 개념의 원천입니다. 세 번째 이유는 다변수(multivariate) 경우와 고유한 인수-분해 도메인(unique factorization domain)에서 계수에 대해 이론과 알고리듬이 이 특정 경우를 강하게 기반으로 합니다. 마지막이지만 가장 작지는 않은, 다항식 GCD 알고리듬과 파생된 알고리듬은 그들의 계산없이 다항식의 근에 대한 유용한 정보를 얻는 것을 허용합니다.

Euclidean division

GCD 계산에 대해, 유클리드의 알고리듬(Euclid's algorithm)에서 사용되는, 다항식의 유클리드 나눗셈은 정수의 유클리드 나눗셈(Euclidean division)과 매우 유사합니다. 그것의 존재는 다음 이론을 기반으로 합니다: 필드에 걸쳐 정의된 두 일변수 다항식 a와 b ≠ 0가 주어지면, 두 다항식 q (몫) 및 r (나머지)가 존재하며 이것은 다음을 만족시킵니다:

필드에 대해 정의된 두 개의 일 변량 다항식 a와 b ≠ 0이 주어지면 두 가지 다항식 q (몫)와 r (나머지)이 충족됩니다.

a=bq+r

및

\deg(r)<\deg(b),

여기서 "deg(...)"는 차수를 나타내고 영 다항식의 차수는 음인 것으로 정의됩니다. 게다가, q와 r은 이들 관계에 의해 고유하게 정의됩니다.

정수의 유클리드 나눗셈과의 차이는, 정수에 대해, 차수가 절댓값에 의해 대체되고, 고유성을 가지기 위해 우리는 r이 비-음인 것으로 가정해야 한다는 것입니다. 그러한 정리가 존재하는 링은 유클리드 도메인(Euclidean domain)으로 불립니다.

정수에 대한 것과 마찬가지로, 다항식의 유클리드 나눗셈은 긴 나눗셈(long division) 알고리듬에 의해 계산될 수 있습니다. 이 알고리듬은 보통 종이-와-연필 계산을 위해 제공되지만, 다음과 같이 공식화될 때, 컴퓨터에서 잘 작동합니다 (변수의 이름은 긴 나눗셈의 연필-과-종이 계산에서 종이 판의 영역과 정확히 대응한다는 것에 주목하십시오). 다음 계산에서, "deg"는 (관례 deg(0) < 0와 함께) 그것의 인수의 차수를 의미하고, "lc"는 선행 계수, 변수의 가장 높은 차수의 계수를 의미합니다.

Euclidean division

Input: a and b ≠ 0 two polynomials in the variable x;
Output: q, the quotient, and r, the remainder;

Begin
    q := 0
    r := a
    d := deg(b)
    c := lc(b)
    while deg(r) ≥ d do
        s := lc(r)/c x^deg(r)−d
        q := q + s
        r := r − sb
    end do
    return (q, r)
end.

이 알고리듬의 유효성에 대한 증명은 전체 "while" 루프 동안, 우리는 $a = bq + r$ 을 가지고 $deg(r)$ 은 각 반복에서 감소하는 비-음의 정수라는 사실에 의존합니다. 따라서 이 알고리듬의 유효성의 증명은 유클리드 나눗셈의 유효성을 역시 입증합니다.

Euclid's algorithm

정수에 대한 것처럼, 유클리드 나눗셈은 GCD 계산에 대해 유클리드 알고리듬(Euclid's algorithm)을 정의하는 것을 허용합니다.

두 다항식 a와 b에서 시작하여, 유클리드의 알고리듬은 쌍 $(a, b)$ 를 $(b, rem(a, b))$ 로 재귀적으로 대체하는 것으로 b = 0까지 구성됩니다 (여기서 " $rem(a, b)$ "는 유클리드 나눗셈의 나머지를 나타내고, 이전 섹션의 알고리듬에 의해 계산됩니다). GCD는 마지막 비-영 나머지입니다.

유클리드의 알고리듬은 다음과 같은 재귀 프로그래밍 스타일에서 공식화될 수 있습니다:

$\gcd(a,b):={\text{if }}b=0{\text{ then }}a{\text{ else }}\gcd(b,\operatorname {rem} (a,b)).$

명령형 프로그래밍 스타일에서, 같은 알고리듬이 되며, 각 중간 나머지에 이름을 제공합니다:

 ${\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}$ 

for ( $i:=1$ ;  $r_{i}\neq 0$ ;  $i:=i+1$ ) do
   ${\begin{aligned}r_{i+1}&:=\operatorname {rem} (r_{i-1},r_{i})\end{aligned}}$ 
end do

return  $(r_{i-1}).$

$r i$ 의 차수의 수열은 엄격하게 감소합니다. 따라서, 많아야, $deg(b)$ 단계 후에, 우리는 영 나머지, 말하자면 $r k$ 를 얻습니다. $(a, b)$ 와 $(b, rem(a, b))$ 는 같은 약수를 가지므로, 공통 약수의 집합은 유클리드 알고리듬에 의해 변경되지 않고 따라서 모든 쌍 $(r i, r i +1)$ 은 공통 약수의 같은 집합을 가집니다. $a$ 와 $b$ 의 공통 약수는 따라서 $r k -1$ 와 0의 공통 약수입니다. 따라서 $r k -1$ 는 $a$ 와 $b$ 의 GCD입니다. 이것은 유클리드의 알고리듬이 GCD를 계산함을 입증할뿐만 아니라, GCD가 존재함을 입증합니다.

Bézout's identity and extended GCD algorithm

베주의 항등식(Bézout's identity)은 GCD와 관련된 정리이며, 처음에는 정수에 대해 증명되었으며, 이것은 모든 각 주요 아이디얼 도메인(principal ideal domain)에 유효합니다. 필드에 걸쳐 일변수 다항식의 경우에서, 그것은 다음과 같이 표시될 수 있습니다.

만약 $g$ 가 두 다항식 $a$ 와 $b$ (둘 다 영이 아님)의 최대 공통 약수이면, 다음을 만족하는 두 다항식 $u$ 와 $v$ 가 있습니다:

$au+bv=g\quad$ (Bézout's identity)

및 $u = 1, v = 0$ , 또는 $u = 0, v = 1$ , 또는

$\deg(u)<\deg(b)-\deg(g),\quad \deg(v)<\deg(a)-\deg(g).$

다항식의 경우에서, 이 결과의 관심은 다항식 $u$ 와 $v$ 를 계산하기 위해 효율적인 알고리듬이 있다는 것입니다. 이 알고리듬은 루프의 각 반복에서 수행되는 몇 개의 추가 계산에 의해 유클리드의 알고리듬과 다릅니다. 그러므로, 이것을 확장된 GCD 알고리듬이라고 불립니다. 유클리드 알고리듬과의 또 다른 차이점은 유클리드 나눗셈의 오직 나머지 대신에 "quo"로 표시된 몫을 역시 사용한다는 것입니다. 이 알고리듬은 다음과 같이 작동합니다.

Extended GCD algorithm

Input:  $a$ ,  $b$ , univariate polynomials

Output:
   $g$ , the GCD of  $a$  and  $b$ 
   $u$ ,  $v$ , as in above statement
   $a 1$ ,  $b 1$ , such that
     ${\begin{aligned}a=ga_{1}\\b=gb_{1}\end{aligned}}$ 
Begin
   ${\begin{array}{ll}r_{0}=a&r_{1}=b\\s_{0}=1&s_{1}=0\\t_{0}=0&t_{1}=1\end{array}}$ 
  
  for ( $i = 1$ ;  $r i \neq 0$ ;  $i = i +1$ ) do
     $q=\operatorname {quo} (r_{i-1},r_{i})$ 
     ${\begin{aligned}r_{i+1}&=r_{i-1}-qr_{i}\\s_{i+1}&=s_{i-1}-qs_{i}\\t_{i+1}&=t_{i-1}-qt_{i}\end{aligned}}$ 
  end do
   ${\begin{aligned}g&=r_{i-1}\\u&=s_{i-1}\\v&=t_{i-1}\end{aligned}}$ 
   ${\begin{aligned}a_{1}&=(-1)^{i-1}t_{i}\\b_{1}&=(-1)^{i}s_{i}\end{aligned}}$ 
end.

알고리듬이 출력 사양을 만족시킨다는 증명은, 모든 각 $i$ 에 대해, 우리가 다음을 가진다는 사실에 의존합니다:

r_{i}=as_{i}+bt_{i}

s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},

후자 상등은 다음을 의미합니다:

s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.

차수에 대한 주장은, 모든 각 반복에서, $s i$ 와 $t i$ 의 차수가 $s i$ 의 차수가 감소할 때 최대로 증가한다는 사실을 따릅니다.

이 알고리듬의 흥미로운 특징은, 베주의 항등식의 계수가 필요할 때, 우리는 그들의 GCD에 의해 입력 다항식의 몫을 무료로 얻는다는 것입니다.

Arithmetic of algebraic extensions

확장된 GCD 알고리듬의 중요한 응용은 대수적 필드 확장(algebraic field extension)에서 나눗셈을 계산하는 것을 허용한다는 것입니다.

$L$ 을 최소 다항식 $f$ 가 차수 $n$ 을 갖는 원소에 의해 생성된 필드 $K$ 의 대수적 확장으로 놓습니다. $L$ 의 원소는 보통 $n$ 보다 작은 차수의 $K$ 에 걸쳐 일변수 다항식에 의해 표시됩니다.

$L$ 에서 덧셈은 단순히 다항식의 덧셈입니다:

a+_{L}b=a+_{K[X]}b.

$L$ 에서 곱셈은 $f$ 에 의한 나눗셈을 따르는 다항식의 곱셈입니다:

a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).

$L$ 의 비-영 원소 $a$ 의 역수는 베주의 항등식 $au + fv = 1$ 에서 계수 $u$ 이며, 이것은 확장된 GCD 알고리듬에 의해 계산될 수 있습니다. (GCD는 1인데 왜냐하면 최소 다항식 $f$ 는 기약이기 때문입니다). 확장된 GCD 알고리듬의 사양에서 차수 부등식은 $f$ 에 의한 추가 나눗셈이 deg( $u$ ) < deg( $f$ )를 얻기 위해 요구되지 않음을 보여줍니다.

Subresultants

일변수 다항식의 경우에서, 최대 공통 약수와 결과식(resultant) 사이에 강한 관계가 있습니다. 사실, 두 다항식 P, Q의 결과식은 값 영을 가지는 P와 Q의 계수의 다항식 함수인 것과 P와 Q의 GCD가 상수가 아닌 것은 필요충분 조건입니다.

부분-결과식 이론은 두 다항식의 일반적으로 GCD를 특성화하는 것을 허용하는 이 속성의 일반화이고, 결과식은 0-번째 부분-결과식 다항식입니다.^[1]

두 다항식 P와 Q의 i-번째 부분-결과 다항식 S_i(P ,Q)는 그의 계수가 P와 Q의 계수의 다항 함수인 많아야 i 차수의 다항식이고, i-번째 주요 부분-결과식 계수 s_i(P ,Q)는 S_i(P, Q)의 차수 i의 계수입니다. 그들은 P와 Q의 GCD가 차수 d를 가지는 것과 다음인 것은 필요충분 조건이라는 속성을 가집니다:

s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0\ ,s_{d}(P,Q)\neq 0

.

이 경우에서, S_d(P, Q)는 P와 Q의 GCD이고 다음입니다:

S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.

부분-결과 다항식의 모든 각 계수는 P와 Q의 실베스터 행렬(Sylvester matrix)의 부분-행렬의 행렬식으로 정의됩니다. 이것은 부분-결과식이 잘 "특수화됨"을 의미합니다. 보다 정확하게, 부분-결과식은 임의의 교환 링 R에 걸쳐 다항식에 대해 정의되고, 다음 속성을 가집니다.

φ를 R에서 또 다른 교환 링 S로의 링 준동형으로 놓습니다. 그것은 R과 S에 걸쳐 다항식 사이의 역시 φ로 표시되는, 또 다른 준동형으로 확장됩니다. 그런-다음, 만약 P와 Q가 다음을 만족하는 R에서 계수를 갖는 일변수 다항식이면:

\deg(P)=\deg(\varphi (P))

및

\deg(Q)=\deg(\varphi (Q)),

φ(P)와 φ(Q)의 부분-결과 다항식과 주요 부분-결과식 계수는 P와 Q의 그들의 φ에 의한 이미지입니다.

부분-결과식은 정수 계수를 갖는 두 다항식의 GCD 컴퓨터에서 계산하는 것에 기본을 만드는 두 가지 중요한 속성을 가집니다. 첫째, 행렬식을 통한 그들의 정의는 아다마르 부등식(Hadamard inequality)을 통해 GCD 계수의 크기를 경계짓는 것을 허용합니다. 둘째, 이 경계와 좋은 특성화의 속성은 모듈러 계산(modular computation)과 중국의 나머지 정리(Chinese remainder theorem)를 통해 정수 계수를 갖는 두 다항식의 GCD를 계산하는 것을 허용합니다 (아래를 참조하십시오).

Technical definition

P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X^{n}.

을 필드 K에서 계수를 갖는 일변수 다항식으로 놓습니다. 차원 i의 K 벡터 공간을 i보다 작은 차수의 다항식을 ${\mathcal {P}}_{i}$ 으로 나타냅니다. i ≤ m 및 i ≤ n을 만족하는 비-음 정수에 대해, 다음

\varphi _{i}:{\mathcal {P}}_{n-i}\times {\mathcal {P}}_{m-i}\rightarrow {\mathcal {P}}_{m+n-i}

을 다음을 만족하는 선형 맵으로 놓습니다:

\varphi _{i}(A,B)=AP+BQ.

P와 Q의 결과식(resultant)은 실베스터 행렬(Sylvester matrix)의 행렬식이며, 이것은 X의 거듭-제곱의 기초 위에 $\varphi _{0}$ 의 (정사각) 행렬입니다. 비슷하게, i-부분결과 다항식은 $\varphi _{i}$ 의 행렬의 부분-행렬의 행렬식의 관점에서 정의됩니다.

이 행렬을 보다 정확하게 설명하겠습니다;

i < 0 또는 i > m에 대해 p_i = 0로 놓고, i < 0 또는 i > n에 대해 q_i = 0로 놓습니다. 실베스트 행렬은 i-번째 행과 j-번째 열의 계수가 j ≤ n에 대해 p_m+j−i이고 j > n에 대해 q_j−i를 만족하는 (m + n) × (m + n)-행렬입니다:^[2]

S={\begin{pmatrix}p_{m}&0&\cdots &0&q_{n}&0&\cdots &0\\p_{m-1}&p_{m}&\cdots &0&q_{n-1}&q_{n}&\cdots &0\\p_{m-2}&p_{m-1}&\ddots &0&q_{n-2}&q_{n-1}&\ddots &0\\\vdots &\vdots &\ddots &p_{m}&\vdots &\vdots &\ddots &q_{n}\\\vdots &\vdots &\cdots &p_{m-1}&\vdots &\vdots &\cdots &q_{n-1}\\p_{0}&p_{1}&\cdots &\vdots &q_{0}&q_{1}&\cdots &\vdots \\0&p_{0}&\ddots &\vdots &0&q_{0}&\ddots &\vdots &\\\vdots &\vdots &\ddots &p_{1}&\vdots &\vdots &\ddots &q_{1}\\0&0&\cdots &p_{0}&0&0&\cdots &q_{0}\end{pmatrix}}.

$\varphi _{i}$ 의 행렬 T_i는 S의 (m + n − i) × (m + n − 2i)-부분행렬이며 이것은 S의 1에서 n − i와 n + 1에서 m + n − i까지 열 1의 부분-행렬에서 영들의 마지막 i 행을 제거함으로써 얻습니다 (즉, 각 블럭에서 i 열과 영들의 i 마지막 행을 제거합니다). 주요 부분-결과 계수 s_i는 T_i의 m + n − 2i 첫 번째 행의 행렬식입니다.

V_i를 다음과 같이 정의된 (m + n − 2i) × (m + n − i) 행렬로 놓습니다. 먼저 우리는 (m + n − 2i − 1) × (m + n − 2i − 1) 항등 행렬(identity matrix)의 오른쪽에 영들의 (i + 1) 열을 더합니다. 그런-다음 우리는 결과 행렬의 아래에 Xⁱ, Xⁱ⁻¹, ..., X, 1을 따르는 (m + n − i − 1) 영들로 구성되는 행으로 경계를 정합니다:

V_{i}={\begin{pmatrix}1&0&\cdots &0&0&0&\cdots &0\\0&1&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\ddots &\vdots &0\\0&0&\cdots &1&0&0&\cdots &0\\0&0&\cdots &0&X^{i}&X^{i-1}&\cdots &1\end{pmatrix}}.

이 표기법과 함께, i-번째 부분-결과 다항식은 행렬 곱 V_iT_i의 행렬식입니다. 차수 j의 그것의 계수는 그것의 m + n − 2i − 1 처음 행과 (m + n − i − j)-번째 행으로 구성되는 T_i의 정사각 부분-행렬의 행렬식입니다.

Sketch of the proof

정의된 것처럼, 부분-결과식이 원하는 속성을 갖는 것은 분명하지 않습니다. 실제로, 그 증명은 만약 선형 대수의 속성과 다항식의 속성이 합쳐지면 다소 간단합니다.

정의된 것처럼, 행렬 T_i의 열은 $\varphi _{i}$ 의 이미지에 속하는 일부 다항식의 계수의 벡터입니다. i-번째 부분-결과 다항식 S_i의 정의는 그것의 계수의 벡터가 이들 열 벡터의 선형 조합이라는 것, 및 따라서 S_i는 $\varphi _{i}$ 의 이미지에 속한다는 것을 보여줍니다.

만약 GCD의 차수가 i보다 크면, 베주의 항등식(Bézout's identity)은 $\varphi _{i}$ 의 이미지에서 보든 각 비-영 다항식은 i보다 더 큰 차수를 가짐을 보여줍니다. 이것은 S_i=0임을 의미합니다.

만약, 다른 한편으로, GCD의 차수가 i이면, 베주의 항등식은 다시 m + n − i보다 낮은 차수를 가지는 GCD의 배수가 $\varphi _{i}$ 의 이미지에서 있음을 제공함을 허용합니다. 이들 배수의 벡터 공간은 차원 m + n − 2i을 가지고 i보다 작지 않은 쌍별 다른 차수의 다항식의 기초를 가집니다. 이것은 T_i의 열 사다리꼴 형식의 m + n − 2i의 첫 번째 행의 부분-행렬이 항등 행렬이고 따라서 s_i가 0이 아님을 의미합니다. 따라서 S_i는 $\varphi _{i}$ 의 이미지에서 다항식이며, 이것은 GCD의 배수이고 같은 차수를 가집니다. 그것은 따라서 최대 공통 약수입니다.

GCD and root finding

Square-free factorization

대부분의 근-찾기 알고리듬(root-finding algorithm)은 중복 근(multiple root)을 가지는 다항식에서 나쁘게 작동합니다. 따라서 근-찾기 알고리듬을 호출하기 전에 이것을 감지하고 제거하는 것이 유용합니다. GCD 계산은 중복 근의 존재의 감지를 허용하는데, 왜냐하면 다항식의 중복 근은 다항식과 그것의 도함수(derivative)의 GCD의 근이기 때문입니다.

다항식과 그것의 도함수의 GCD를 계산한 후, 추가 GCD 계산은 다항식의 완전한 제곱-없는 인수-분해를 제공하며, 이것은 다음 인수-분해입니다:

f=\prod _{i=1}^{\deg(f)}f_{i}^{i}

여기서, 각 i에 대해, 다항식 f_i는 만약 f가 중복도 i의 임의의 근을 가지지 않으면 1, 또는 그의 근이 f의 중복도 i의 정확하게 근인 제곱-없는 다항식 (즉, 중복 근없는 다항식)입니다 (윤의 알고리듬(Yun's algorithm)을 참조하십시오).

따라서 제곱-없는 인수-분해는 중복 근을 갖는 다항식의 근 찾기를 더 낮은 차수의 여러 제곱-없는 다항식의 근 찾기로 줄입니다. 제곱-없는 인수-분해는 대부분 다항식 인수-분해(polynomial factorization) 알고리짐의 역시 첫 번째 단계입니다.

Sturm sequence

실수 계수를 갖는 다항식의 스튀름 수열(Sturm sequence)은 다항식과 그것의 도함수에 적용되는 유클리드의 알고리듬의 변형에 의해 제공되는 나머지의 수열입니다. 스튀름 수열을 얻는 것에 대해, 우리는 유클리드의 알고리듬의 다음 명령

r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})

을 간단히 다음에 의해 대체합니다:

r_{i+1}:=-\operatorname {rem} (r_{i-1},r_{i}).

V(a)를 점 a에서 평가할 때 부호의 변화의 숫자로 놓습니다. 스튀름의 정리는 V(a) − V(b)가 구간 [a, b]에서 다항식의 실수 근의 숫자임을 주장합니다. 따라서 스튀름 수열은 주어진 구간에서 실수 근의 숫자를 계산하는 것을 허용합니다. 모든 각 부분-구간이 많아야 하나의 근을 포함할 때까지 구간을 세분화함으로써, 이것은 임의의 작은 길이의 구간에서 실수 근을 탐색하는 알고리듬을 제공합니다.

GCD over a ring and over its field of fractions

이 섹션에서, 우리는 고유한 인수-분해 도메인(unique factorization domain) R, 전형적으로 정수의 링, 및 분수의 필드(field of fractions) F, 전형적으로 유리수의 필드에 걸쳐 다항식을 고려하고, 우리는 이들 링에 걸쳐 변수의 집합에서 다항식의 링 R[X] 및 F[X]을 나타냅니다.

Primitive part–content factorization

"cont(p)"로 표시되는 다항식 p ∈ R[X]의 컨텐츠는 그것의 계수의 GCD입니다. 다항식 q ∈ F[X]는 다음으로 쓸 수 있습니다:

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

여기서 p ∈ R[X] and c ∈ R: 그것은 c에 대해 q의 계수의 모든 분모의 배수를 취하는 것으로 충분하고 p = cq입니다. q의 컨텐츠는 다음과 같이 정의됩니다:

\operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.

둘 다 경우에서, 컨텐츠는 R의 단위(unit)에 의해 곱셈까지 정의됩니다.

R[X] 또는 F[X]에서 다항식의 원시 부분은 다음에 의해 정의됩니다:

\operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.

둘 다 경우에서, 그것은 R[X]에서 다항식이며 즉 원시이며, 이것은 1이 그것의 계수의 GCD임을 의미합니다.

따라서 R[X] 또는 F[X]에서 모든 각 다항식은 다음으로 인수화 될 수 있습니다:

p=\operatorname {cont} (p)\,\operatorname {primpart} (p),

그리고 이 인수-분해는 R의 단위에 의해 컨텐츠와 이 단위의 역에 의한 원시 부분의 곱셈까지 고유합니다.

가우스의 보조-정리는 두 원시 다항식의 곱이 원시임을 의미합니다. 그것은 다음임을 따릅니다:

\operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)

및

\operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).

Relation between the GCD over R and over F

이전 섹션의 관계는 R[X] 및 F[X]에서 GCD 사이의 강한 관계를 의미합니다. 모호성을 피하기 위해, 표기법 "gcd"는, 다음에서, GCD가 계산되는 링에 의해 색인화될 것입니다.

만약 q₁와 q₂가 F[X]에 속하면,

\operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).

만약 p₁와 p₂가 R[X]에 속하면,

\gcd _{R[X]}(p_{1},p_{2})=\gcd _{R}(\operatorname {cont} (p_{1}),\operatorname {cont} (p_{2}))\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2})),

및

\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[X]}(p_{1},p_{2})).

따라서 다항식 GCD의 계산은 F[X]에 걸쳐 및 R[X]에 걸쳐 본질적으로 같은 문제입니다.

유리수에 걸쳐 일변수 다항식에 대해, 우리는 유클리드의 알고리듬이 GCD를 계산하는 편리한 방법이라고 생각할 수 있습니다. 어쨌든, 그것은 많은 숫자의 정수의 분수를 단순화하는 것을 포함하고, 결과 알고리듬은 효율적이지 않습니다. 이 이유에 대해, 방법들이 정수에 걸쳐 다항식에 오직 작용하는 것에 대해 유클리드의 알고리듬을 수정하기 위해 설계되어 왔습니다. 그것들은 소위 유사-나눗셈에 의한 분수를 도입하는 유클리드 나눗셈을 대체하고, 소위 유사-나눗셈 수열에 의한 유클리드의 알고리듬의 나머지 수열을 대체함으로써 구성됩니다 (아래를 참조하십시오).

Proof that GCD exists for multivariate polynomials

이전 섹션에서, 우리는 R[X]에서 다항식의 GCD가 R에서 및 F[X]에서 GCD로부터 추론될 수 있음을 알았습니다. 증명을 자세히 살펴보면 이것은 만약 그들이 R에서 및 F[X]에서 존재하면 R[X]에서 GCD의 존재를 입증하는 것을 허용함을 보여줍니다. 특히, 만약 GCD가 R에서 존재하고, 만약 X가 하나의 변수로 감소하면, 이것은 GCD가 R[X]에서 존재함을 입증합니다 (유클리드의 알고리듬은 F[X]에서 GCD의 존재를 입증합니다).

n 변수에서 다항식은 (n − 1) 변수에서 다항식의 링에 걸쳐 일변수 다항식으로 여길 수 있습니다. 따라서, 변수의 숫자에 대한 재귀는 만약 GCD가 존재하고 R에서 계산될 수 있으면, 그것들이 존재하고 R에 걸쳐 모든 각 다변수 다항식 링에서 계산될 수 있음을 보여줍니다. 특히, 만약 R이 정수의 링 또는 필드이면, GCD는 R[x₁,..., x_n]에서 존재하고, 선행하는 것은 그들을 계산하기 위한 알고리듬을 제공합니다.

고유한 인수 분해 도메인에 걸쳐 다항식 링이 고유한 인수 분해 도메인이라는 증명은 비슷하지만, 그것은 알고리듬을 제공하지 않는데, 왜냐하면 필드에 걸쳐 일변수 다항식을 인수화하기 위한 일반적인 알고리듬이 없기 때문입니다 (일변수 다항식에 대해 임의의 인수-분해 알고리듬이 존재하지 않는 필드의 예제가 있습니다).

Pseudo-remainder sequences

이 섹션에서, 우리는 정수 도메인(integral domain) Z (전형적으로 정수의 링 Z)와 그것의 분수의 필드 Q (전형적으로 유리수의 필드 Q)를 고려합니다. 일변수 다항식 링 Z[X]에서 두 다항식 A와 B가 주어지면, B에 의한 A의 (Q에 걸쳐) 유클리드 나눗셈은 Z[X]에 속하지 않는 몫과 나머지를 제공합니다.

만약 우리가 다음 다항식에 유클리드의 알고리듬을 적용하면^[3]

X^{8}+X^{6}-3X^{4}-3X^{3}+8X^{2}+2X-5

및

3X^{6}+5X^{4}-4X^{2}-9X+21,

유클리드의 알고리듬의 연속적인 나머지는 다음입니다:

{\begin{aligned}&-{\tfrac {5}{9}}X^{4}+{\tfrac {1}{9}}X^{2}-{\tfrac {1}{3}},\\&-{\tfrac {117}{25}}X^{2}-9X+{\tfrac {441}{25}},\\&{\tfrac {233150}{19773}}X-{\tfrac {102500}{6591}},\\&-{\tfrac {1288744821}{543589225}}.\end{aligned}}

우리는, 입력 다항식의 계수의 작은 차수와 작은 크기에도 불구하고, 오히려 큰 크기의 정수 분수를 조작하고 단순화해야 한다는 것을 알 수 있습니다.

유사-나눗셈은 모든 나머지가 Z[X]에 속하는 유클리드 알고리듬의 변형을 허용하기 위해 도입되어 왔습니다.

만약 $\deg(A)=a$ 및 $\deg(B)=b$ 및 a ≥ b이면, B에 의한 A의 유사-나눗셈의 유사-나머지는, prem(A,B)에 의해 표시되며, 다음입니다:

\operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),

여기서 $lc(B)$ 는 B의 선행 계수 (X^b의 계수)입니다.

Z[X]에서 두 다항식의 유사-나눗셈의 유사-나머지는 항상 Z[X]에 속합니다.

유사-나머지 수열은 유클리드의 나눗셈의 다음 명령

r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})

을 다음에 의해 대체함으로써 얻어진 (유사) 나머지 r_i의 수열입니다:

r_{i+1}:={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},

여기서 α는 분자의 정확히 모든 각 계수를 나누는 Z의 원소입니다. α의 다른 선택은 다른 유사-나머지 수열을 제공하며, 이것은 다음 부분-섹션에서 설명됩니다.

두 다항식의 공통 약수가 만약 다항식이 (Q에서) 역-가능한 상수에 의해 곱해지면, 변하지 않기 때문에, 유사-나머지 수열의 마지막 비-영 항은 입력 다항식의 (Q[X]에서) GCD입니다. 그러므로, 유사-나머지 수열은 Q에서 분수를 도입하는 것없이 Q[X]에서 GCD를 계산하는 것을 허용합니다.

일부 문맥에서, 유사-나머지의 선행 계수의 부호를 제어하는 것이 본질적입니다. 이것은 전형적으로 결과식(resultant)과 부분-결과식(subresultant)을 계산할 때, 또는 스튀름의 정리(Sturm's theorem)를 사용하는 것에 대해 경우입니다. 이 제어는 유사-나머지의 정의에서 $lc(B)$ 를 절댓값으로 대체하는 것, 또는 $α$ 의 부호를 제어함으로써 수행될 수 있습니다 (만약 $α$ 가 나머지의 모든 계수를 나누면, 같은 것은 $- α$ 에 대해 참입니다).^[1]

Trivial pseudo-remainder sequence

(정의하는 것에) 가장 간단한 나머지 수열은 항상 $α = 1$ 을 취하는 것으로 구성됩니다. 실제 계산에서, 계수의 크기가 입력 다항식의 차수에 따라 지수적으로 증가하므로, 흥미롭지 않습니다. 이것은 앞의 섹션의 예제에서 명확하게 나타나며, 이것에 대해 연속적인 유사-나머지는 다음입니다:

-15\,X^{4}+3\,X^{2}-9,

15795\,X^{2}+30375\,X-59535,

1254542875143750\,X-1654608338437500,

12593338795500743100931141992187500.

연속적인 나머지의 계수의 자릿수의 숫자는 알고리듬의 각 반복에서 두 배 이상입니다. 이것은 자명한 유사-나머지 수열의 전형적인 동작입니다.

Primitive pseudo-remainder sequence

원시 유사-나머지 수열은 분자의 컨텐츠 α에 대해 취하는 것으로 구성됩니다. 따라서 모든 r_i는 원시 다항식입니다.

원시 유사-나머지 수열은 가장 작은 계수를 생성하는 유사-나머지 수열입니다. 어쨌든 그것은 Z에서 다수의 GCD를 계산하는 것이 요구되고, 그러므로 특히 Z가 다항식 링 자체일 때, 실제 계산에서 사용하기에는 충분히 효율적이지 않습니다.

이전 섹션에서와 같은 입력으로, 그들의 컨텐츠에 의한 나눈 후에, 연속적인 나머지는 다음입니다:

-5\,X^{4}+X^{2}-3,

13\,X^{2}+25\,X-49,

4663\,X-6150,

1.

계수의 작은 크기는 다수의 정수 GCD 및 GCD에 의한 나눗셈이 계산되었다는 사실을 숨깁니다.

Subresultant pseudo-remainder sequence

부분-결과식 수열은 역시 유사-나머지로 계산될 수 있습니다. 이 과정은 모든 각 r_i가 부분-결과 다항식인 그런 방법에서 α를 선택하는 것으로 구성됩니다. 놀랍게도, α의 계산은 매우 쉽습니다 (아래 참조하십시오). 다른 한편으로, 알고리듬의 정확성의 증명은 어려운데, 왜냐하면 두 연속적인 나머지의 차수의 차이에 대해 모든 가능성을 고려해야 하기 때문입니다.

부분-결과 수열에서 계수는 원시 유사-나머지 수열의 그것보다 드물게 더 큽니다. Z에서 GCD 계산은 필요되지 않기 때문에, 유사-나머지를 갖는 부분-결과 수열은 가장 효율적인 계산을 제공합니다.

이전 섹션에서와 같은 입력으로, 연속적인 나머지는 다음입니다:

15\,X^{4}-3\,X^{2}+9,

65\,X^{2}+125\,X-245,

9326\,X-12300,

260708.

그 계수는 합리적인 크기를 가집니다. 그들은 GCD 계산없이 오직 정확한 나눗셈에서 얻습니다. 이것은 이 알고리듬을 원시 유사-나머지 수열보다 효율적으로 만듭니다.

유사-나머지를 갖는 부분-결과 수열을 계산하는 알고리듬은 아래에 제공됩니다. 이 알고리듬에서, 입력 $(a, b)$ 는 Z[X]에서 다항식의 쌍입니다. $r i$ 는 Z[X]의 연속적인 유사-나머지, 변수 i와 $d i$ 는 비-음의 정수이고, 그리스 문자는 Z에서 원소를 나타냅니다. 함수 deg() 및 rem()은 다항식의 차수와 유클리드 나눗셈의 나머지를 나타냅니다. 이 알고리듬에서, 이 나머지는 항상 Z[X] 안에 있습니다. 마지막으로, 표시된 나눗셈 /는 항상 정확하고 Z[X] 또는 Z에서 그들의 결과를 가집니다.

 ${\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}$ 
for ( $i:=1$ ;  $r_{i}\neq 0$ ;  $i:=i+1;$ ) do
   ${\begin{aligned}d_{i}&:=\deg(r_{i-1})-\deg(r_{i})\\\gamma _{i}&:=\operatorname {lc} (r_{i})\end{aligned}}$ 
  if  $i=1$  then
     ${\begin{aligned}\beta _{1}&:=(-1)^{d_{1}+1}\\\psi _{1}&:=-1\end{aligned}}$ 
  else
     ${\begin{aligned}\beta _{i}&:=-\gamma _{i-1}\psi _{i}^{d_{i}}\\\psi _{i}&:={\frac {(-\gamma _{i-1})^{d_{i-1}}}{\psi _{i-1}^{d_{i-1}-1}}}\end{aligned}}$ 
  end if
   $r_{i+1}:={\frac {\operatorname {rem} (\gamma _{i}^{d_{i}+1}r_{i-1},r_{i})}{\beta _{i}}}$ 
end do.

주목: "lc"는 선행 계수, 변수의 가장 높은 차수의 계수를 의미합니다.

이 알고리듬은 최대 공통 약수 (마지막으로 비-영 $r i$ )뿐만 아니라, 모든 부분-결과 다항식을 계산합니다: 나머지 $r i$ 는 $(deg(r i -1) - 1)$ -번째 부분-결과 다항식입니다. 만약 $deg(r i) < deg(r i -1) - 1$ 이면, $deg(r i)$ -번째 부분-결과 다항식은 $lc(r i) deg(r i -1)-deg(r i)-1 r i$ 입니다. 모든 다른 부분-결과 다항식은 영입니다.

Sturm sequence with pseudo-remainders

우리는 스튀름 수열(Sturm sequence)과 같은 속성을 갖는 수열을 구성하는 것에 대해 유사-나머지를 사용할 수 있습니다. 이것은 스튀름 수열에서 처럼 같은 부호를 갖기 위해 연속적인 유사-나머지의 부호를 제어하는 것이 요구됩니다. 이것은 다음과 같이 수정된 유사-나머지를 정의함으로써 행해질 수 있습니다.

만약 $\deg(A)=a$ 및 $\deg(B)=b$ 및 a ≥ b이면, B에 의한 A의 유사-나눗셈의 수정된 유사-나머지 prem2(A, B)는 다음입니다:

\operatorname {prem2} (A,B)=-\operatorname {rem} (|\operatorname {lc} (B)|^{a-b+1}A,B),

여기서 |lc(B)|는 B의 선행 계수 (X^b의 계수)의 절댓값입니다.

정수 계수를 갖는 입력 다항식에 대해, 이것은 정수 계수를 갖는 다항식으로 구성된 스튀름 수열을 검색하는 것을 허용합니다. 부분-결과 유사-나머지 수열은 유사하게 수정될 수 있으며, 이 경우에서 나머지의 부호는 유리수에 걸쳐 계산된 것과 일치합니다.

위에서 주어진 부분-결과 유사-나머지 수열을 계산하는 것에 대해 알고리듬은 만약 우리가 $\operatorname {prem} (A,B)$ 대신에 $-\mathrm {prem2} (A,B)$ 을 사용하면 틀린 부분-결과 다항식을 계산할 것입니다.

Modular GCD algorithm

만약 f와 g가 어떤 유한하게 생성된 필드 F에 대해 F[x]에서 다항식이면, 유클리드 알고리듬이 그들의 GCD를 계산하기 위한 가장 자연스러운 방법입니다. 어쨌든, 현대 컴퓨터 대수(computer algebra) 시스템은 만약 중간 표현 팽창(intermediate expression swell)으로 불리는 현상으로 인해 F가 유한이며 그것을 오직 사용합니다. 비록 차수가 유클리드 알고리듬 동안 계속 감소하지만, 만약 F가 유한(finite)이 아니면, 다항식의 비트-크기는, F에서 반복된 산술 연산이 더 큰 표현으로 이어지는 경향이기 때문에 계산 동안 (때때로 극적으로) 증가할 수 있습니다. 예를 들어, 그들의 분모가 b에 의해 경계지는 두 유리수의 덧셈은 그들의 분모가 b²에 의해 경계지는 유리수로 이어지므로, 최악의 경우에서, 비트-크기는 단지 한 번의 연산으로 거의 두 배가 될 수 있습니다.

계산을 촉진하기 위해, f와 g가 D[x]에 있는 링 D를 취하고, D/I가 유한 링을 만족하는 아이디얼 I을 취합니다. 그런-다음 유클리드 알고리듬과 함께 이 유한 링에 걸쳐 GCD를 계산합니다. 재구성 기술 (중국의 나머지 정리(Chinese remainder theorem), 유리수 재구성(rational reconstruction), 등)을 사용하여, 우리는 아이디얼 I의 이미지 모듈로 숫자에서 f와 g의 GCD를 복구할 수 있습니다. 이것이 우리가 비-최소 차수를 갖는 모듈러 이미지를 버리고, 선행 계수가 사라지는 아이디얼 I를 피하는 것에 의해 제공되면 동작함을 입증할 수 있습니다.^[4]

$F=\mathbb {Q} ({\sqrt {3}})$ , $D=\mathbb {Z} [{\sqrt {3}}]$ , $f={\sqrt {3}}x^{3}-5x^{2}+4x+9$ 및 $g=x^{4}+4x^{2}+3{\sqrt {3}}x-6$ 를 가정합니다. 만약 우리가 $I=(2)$ 를 취하면, $D/I$ 는 유한 링(finite ring)입니다 (필드는 아닌데 왜냐하면 $I$ 는 $D$ 에서 최대가 아니기 때문입니다). $(D/I)[x]$ 에서 $f,g$ 의 이미지에 적용된 유클리드 알고리듬은 성공하고 1을 반환합니다. 이것은 $F[x]$ 에서 $f,g$ 의 GCD가 마찬가지로 1이어야 함을 의미합니다. 이 예제는 차수가 표현 팽창에 대해 발생하기에 너무 작기 때문에 임의의 방법에 의해 쉽게 처리될 수 있지만, 만약 두 다항식이 GCD 1을 가지면, 모듈러 알고리듬이 단일 아이디얼 $I$ 후에 종료될 가능성이 있음을 묘사함을 주목하십시오.

References

^ ^a ^b Basu, Pollack & Roy 2006
^ Many author define the Sylvester matrix as the transpose of S. This breaks the usual convention for writing the matrix of a linear map.
^ Knuth 1969
^ van Hoeij & Monagan 2004

Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006). Algorithms in real algebraic geometry, chapter 4.2. Springer-Verlag. {{cite book}}: Invalid |ref=harv (help)
Davenport, James H.; Siret, Yvon; Tournier, Évelyne (1988). Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. Academic Press. ISBN 978-0-12-204230-0. {{cite book}}: Invalid |ref=harv (help)
van Hoeij, M.; Monagan, M.B. (2004), Algorithms for polynomial GCD computation over algebraic function fields, pp. 297–304 {{citation}}: Unknown parameter |conference= ignored (help)
Javadi, S.M.M.; Monagan, M.B. (2007), A sparse modular GCD algorithm for polynomials over algebraic function fields, pp. 187–194 {{citation}}: Unknown parameter |conference= ignored (help)
Knuth, Donald E. (1969). The Art of Computer Programming II. Addison-Wesley. pp. 370–371. {{cite book}}: Invalid |ref=harv (help)
Knuth, Donald E. (1997). 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. {{cite book}}: Invalid |ref=harv (help)
Loos, Rudiger (1982), "Generalized polynomial remainder sequences", in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag

[BPR-1] Basu, Pollack & Roy 2006

[2] Many author define the Sylvester matrix as the transpose of S. This breaks the usual convention for writing the matrix of a linear map.

[3] Knuth 1969

[4] van Hoeij & Monagan 2004

[1]

[2]

[3]

[4]