Extended Euclidean algorithm

산술(arithmetic)과 컴퓨터 프로그래밍(computer programming)에서, 확장된 유클리드 알고리듬(extended Euclidean algorithm)은 유클리드 알고리듬에 대한 확장이고, 정수 a와 b의 최대 공통 약수 (gcd) 외에도 다음임을 만족하는 정수 x와 y인 베주의 항등식(Bézout's identity)의 계수도 계산합니다:

ax+by=\gcd(a,b).

이것은 gcd가 이 방정식을 동시에 만족시키고 입력을 나눌 수 있는 유일한 숫자이기 때문에 인증하는 알고리듬(certifying algorithm)입니다. 그것은 역시, 거의 추가 비용 없이 최대 공통 약수로 a와 b의 몫을 계산하도록 허용합니다.

확장된 유클리드 알고리듬(Extended Euclidean algorithm)은 역시 다항식 최대 공통 약수와 두 일변수 다항식(univariate polynomials)의 베주의 항등식 계수를 계산하기 위한 매우 유사한 알고리듬을 참조합니다.

확장된 유클리드 알고리듬은 a와 b가 서로소(coprime)일 때 특히 유용합니다. 해당 규정과 함께, x는 a 모듈로 b의 모듈러 곱셈 역이고, y는 b 모듈로 a의 모듈러 곱셈 역입니다. 유사하게, 다항식 확장된 유클리드 알고리듬은 대수적 필드 확장(algebraic field extensions)과 특히 비 소수 차수의 유한 필드(finite fields)에서 곱셈 역(multiplicative inverse)을 계산하는 것을 허용합니다. 역시 확장된 유클리드 알고리듬 둘 다는 암호화(cryptography)에 널리 사용됩니다. 특히, 모듈러 곱셈 역(modular multiplicative inverse)의 계산은 RSA 공개-키 암호화 방법에서 키-쌍 도출에 있어 필수적인 단계입니다.

Description

표준 유클리드 알고리듬은 몫이 사용되지 않는 일련의 유클리드 나눗셈(Euclidean divisions)에 의해 진행됩니다. 오직 나머지가 유지됩니다. 확장된 알고리듬에 대해, 연속적인 몫이 사용됩니다. 보다 정확하게, a와 b를 입력으로 하는 표준 유클리드 알고리듬은 다음임을 만족하는 몫의 순서열 $q_{1},\ldots ,q_{k}$ 와 나머지의 순서열 $r_{0},\ldots ,r_{k+1}$ 을 계산하는 것으로 구성됩니다:

{\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{and}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(this defines }}q_{i})\\&\,\,\,\vdots \end{aligned}}

오른쪽의 부등식이 $r_{i-1}$ 와 $r_{i}$ 에서 고유하게 $q_{i}$ 와 $r_{i+1}$ 을 정의하는 것이 유클리드 나눗셈(Euclidean division)의 주요 속성입니다.

그 계산은 영인 나머지 $r_{k+1}$ 에 도달할 때 중지됩니다; 최대 공통 약수는 그때에 마지막 비-영 나머지 $r_{k}$ 입니다.

확장된 유클리드 알고리듬은 유사하게 진행되지만, 다음과 같이 두 개의 다른 순서열을 추가합니다:

{\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{and }}0&\leq r_{i+1}<|r_{i}|&{\text{(this defines }}q_{i}{\text{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}

그 계산은 역시 $r_{k+1}=0$ 일 때 중지하고 다음을 제공합니다:

$r_{k}$ 는 입력 $a=r_{0}$ 와 $b=r_{1}$ 의 최대 공통 약수입니다.
베주 계수는 $s_{k}$ 와 $t_{k},$ 즉, $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$ 입니다.
최대 공통 약수에 의한 a와 b의 몫은 $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ 와 $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ 에 의해 제공됩니다.

게다가, 만약 a와 b가 모두 양수이고 $\gcd(a,b)\neq \min(a,b)$ 이면, $0\leq i\leq k$ 에 대해 다음과 같습니다:

|s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{and}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor

여기서 $\lfloor x\rfloor$ 는 $x$ 의 정수 부분(integral part), 즉, $x$ 보다 크지 않은 가장 큰 정수를 나타냅니다.

이것은 확장된 유클리드 알고리듬에 의해 제공되는 베주 계수의 쌍이 위의 부등식을 모두 만족시키는 고유한 쌍이므로 베주 계수의 최소 쌍(minimal pair)임을 의미합니다.

역시 그 알고리듬은 a와 b보다 큰 고정 크기의 정수를 사용하는 컴퓨터 프로그램에 의해 정수 오버플로 없이 수행될 수 있음을 의미합니다.

Example

다음 테이블은 확장된 유클리드 알고리듬이 입력 240과 46으로 진행되는 방법을 보여줍니다. 최대 공통 약수는 "나머지(remainder)" 열에서 마지막 비-영 엔트리, 2입니다. 계산은 행 6에서 중지되는데, 왜냐하면 그것에서 나머지가 0이기 때문입니다. 베주 계수는 마지막에서 두 번째 행의 마지막 두 엔트리에 나타납니다. 사실, −9 × 240 + 47 × 46 = 2임을 확인하는 것은 쉽습니다. 마지막으로, 마지막 행의 마지막 두 엔트리 23과 −120은, 부호까지, 최대 공통 약수 2에 의한 입력 46과 240의 몫입니다.

index i	quotient q_i−1	Remainder r_i	s_i	t_i
0		240	1	0
1		46	0	1
2	240 ÷ 46 = 5	240 − 5 × 46 = 10	1 − 5 × 0 = 1	0 − 5 × 1 = −5
3	46 ÷ 10 = 4	46 − 4 × 10 = 6	0 − 4 × 1 = −4	1 − 4 × −5 = 21
4	10 ÷ 6 = 1	10 − 1 × 6 = 4	1 − 1 × −4 = 5	−5 − 1 × 21 = −26
5	6 ÷ 4 = 1	6 − 1 × 4 = 2	−4 − 1 × 5 = −9	21 − 1 × −26 = 47
6	4 ÷ 2 = 2	4 − 2 × 2 = 0	5 − 2 × −9 = 23	−26 − 2 × 47 = −120

Proof

$0\leq r_{i+1}<|r_{i}|$ 이기 때문에, $r_{i}$ 의 수열은 (i = 2부터) 비-음의 정수의 감소하는 수열입니다. 따라서 그것은 어떤 $r_{k+1}=0$ 에서 중지해야 합니다. 이것은 알고리듬이 결국 멈춘다는 것을 입증합니다.

$r_{i+1}=r_{i-1}-r_{i}q_{i}$ 이기 때문에, 최대 공통 약수는 $(r_{i-1},r_{i})$ 와 $(r_{i},r_{i+1})$ 에 대해 같습니다. 이것은 입력 $a=r_{0},b=r_{1}$ 의 최대 공통 약수가 $r_{k},r_{k+1}=0$ 의 최대 공통 약수와 같음을 보여줍니다. 이것은 $r_{k}$ 가 a와 b의 최대 공통 약수임을 입증합니다. (이 시점까지, 증명은 고전적인 유클리드 알고리듬의 것과 같습니다.)

$a=r_{0}$ 와 $b=r_{1}$ 이기 때문에, i = 0과 1에 대해 $as_{i}+bt_{i}=r_{i}$ 를 가집니다. 그 관계는 모든 $i>1$ 에 대한 귀납법에 의해 따릅니다:

r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}.

따라서 $s_{k}$ 와 $t_{k}$ 는 베주 계수입니다.

다음 행렬을 생각해 보십시오:

A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.

재귀 관계는 다음 행렬 형식에서 다시 쓸 수 있습니다:

A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}.

행렬 $A_{1}$ 은 항등 행렬이고 그것의 행렬식은 일입니다. 앞의 수식에서 맨 오른쪽 행렬의 행렬식은 −1입니다. 따라서 $A_{i}$ 의 행렬식은 $(-1)^{i-1}$ 입니다. 특히, $i=k+1$ 에 대해, $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}$ 를 가집니다. 이것을 베주의 항등식으로 보면, 이것은 $s_{k+1}$ 과 $t_{k+1}$ 이 서로소(coprime)임을 보여줍니다. 위에서 입증된 $as_{k+1}+bt_{k+1}=0$ 관계와 유클리드의 보조정리(Euclid's lemma)는 $s_{k+1}$ 이 $b$ 를 나눈다, 즉, 어떤 정수 $d$ 에 대해 $b=ds_{k+1}$ 임을 보여줍니다. 관계 $as_{k+1}+bt_{k+1}=0$ 을 $s_{k+1}$ 로 나누는 것은 $a=-dt_{k+1}$ 을 제공합니다. 따라서 $s_{k+1}$ 과 $-t_{k+1}$ 은 공통 인수에 의한 $a$ 와 $b$ 의 몫인 서로소 정수이며, 이는 최대 공통 약수 또는 그것의 반대(opposite)입니다.

마지막 주장을 입증하기 위해, a와 b가 둘 다 양수이고 $\gcd(a,b)\neq \min(a,b)$ 라고 가정합니다. 그런-다음 $a\neq b$ 이고, $a<b$ 이면, EEA 아래에서 (a,b)에 대해 s와 t 수열은, 초기 0들과 1들까지, (b,a)에 대해 t와 s 수열임을 알 수 있습니다. 그런-다음 정의는 (a,b) 경우가 (b,a) 경우로 축소됨을 보여줍니다. 따라서 일반성의 손실 없이 $a>b$ 라고 가정합니다.

$s_{2}$ 는 1이고 $s_{3}$ ( $\gcd(a,b)\neq \min(a,b)$ 에 의해 존재함)는 음의 정수임을 알 수 있습니다. 그 후, $s_{i}$ 는 부호에서 교대하고 크기에서 엄격하게 증가하며, 이는 정의와 $1\leq i\leq k$ 에 대해 $q_{i}\geq 1$ 이라는 사실로부터 귀납적으로 따르며, 경우 $i=1$ 은 $a>b$ 이기 때문에 유지됩니다. 같은 것은 같은 이유로 처음 몇 항 이후의 $t_{i}$ 에 대해 참입니다. 게다가, $q_{k}\geq 2$ (a와 b가 둘 다 양수이고 $\gcd(a,b)\neq \min(a,b)$ 일 때)임을 쉽게 알 수 있습니다. 따라서,

|s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}}\right|\geq 2|s_{k}|\qquad {\text{and}}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}}\right|\geq 2|t_{k}|.

이것은 $s_{k},t_{k}$ 가 각각 임의의 이전의 $s_{i}$ 또는 $t_{i}$ 보다 절댓값이 크거나 같다는 사실과 동반되어 증명을 완료했습니다.

Polynomial extended Euclidean algorithm

필드(field)에서 계수를 갖는 일변수 다항식(univariate polynomials)에 대해, 모든 것, 유클리드 나눗셈, 베주의 항등식, 및 확장된 유클리드 알고리듬이 유사하게 작동합니다. 첫 번째 차이점은 유클리드 나눗셈과 알고리듬에서, 부등식 $0\leq r_{i+1}<|r_{i}|$ 이 차수 $\deg r_{i+1}<\deg r_{i}$ 에 대한 부등식에 의해 대체되어야 합니다. 그렇지 않으면, 단순히 정수를 다항식으로 바꿈으로써 이 기사에서 앞 부분에 있는 모든 내용이 같게 유지됩니다.

두 번째 차이점은 확장된 유클리드 알고리듬에 의해 제공되는 베주 계수의 크기에 대한 경계에 있으며, 이는 다항식의 경우에서 더 정확하며, 다음 정리로 이어집니다.

만약 a와 b가 두 개의 비-영 다항식이면, 확장된 유클리드 알고리듬은 다음임을 만족하는 고유한 다항식의 쌍 (s, t)을 생성합니다:

as+bt=\gcd(a,b)

그리고

\deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).

세 번째 차이점은, 다항식의 경우에서, 최대 공통 약수는 비-영 상수에 의한 곱셈까지만 정의된다는 것입니다. 최대 공통 약수를 모호하지 않게 정의하는 여러 가지 방법이 있습니다.

수학에서, 최대 공통 약수가 일계수 다항식(monic polynomial)이어야 한다는 것이 공통적입니다. 이를 얻기 위해, 출력의 모든 각 원소를 $r_{k}$ 의 선행 계수(leading coefficient)로 나누는 것으로 충분합니다. 이것은, 만약 a와 b가 서로소이면, 베주 부등식의 오른쪽 변에서 1을 얻는 것을 허용합니다. 그렇지 않으면, 임의의 비-영 상수를 얻을 수 있습니다. 컴퓨터 대수학(computer algebra)에서, 다항식은 공통적으로 정수 계수를 가지고, 최대 공통 약수를 정규화하는 이 방법은 너무 많은 분수를 도입하여 편리하지 않습니다.

정수 계수를 갖는 다항식의 경우에서 최대 공통 약수를 정규화하는 두 번째 방법은, 원시(primitive) 최대 공통 약수를 얻기 위해, 모든 각 출력을 $r_{k}$ 의 컨텐츠(content)로 나누는 것입니다. 만약 입력 다항식이 서로소이면, 이 정규화는 역시 1과 같은 최대 공통 약수를 제공합니다. 이 접근 방식의 단점은 많은 분수가 계산 동안 계산되고 단순화되어야 한다는 것입니다.

세 번째 접근 방식은 유클리드 알고리듬을 확장된 유클리드 알고리듬으로 확장하는 것과 유사한 방법으로 하위-결과 유사-나머지 수열(subresultant pseudo-remainder sequences)의 알고리듬을 확장하는 것으로 구성됩니다. 이것은, 정수 계수를 갖는 다항식으로 시작할 때, 계산되는 모든 다항식이 정수 계수를 갖는 것을 허용합니다. 더욱이, 모든 각 계산된 나머지 $r_{i}$ 는 하위-결과 다항식(subresultant polynomial)입니다. 특히, 만약 입력 다항식이 서로소이면, 베주의 항등식은 다음이 됩니다:

as+bt=\operatorname {Res} (a,b),

여기서 $\operatorname {Res} (a,b)$ 는 a와 b의 결과(resultant)를 나타냅니다. 이 형식의 베주의 항등식에서, 공식에서 분모가 없습니다. 만약 결과로 모든 것을 나누면, 그것에서 나타나는 유리수에 대한 명시적인 공통 분모와 함께 고전적인 베주의 항등식을 얻습니다.

Pseudocode

위에서 설명된 알고리듬을 구현하기 위해, 인덱스 변수의 마지막 두 값만 각 단계에서 필요하다는 점을 먼저 언급해야 합니다. 따라서, 메모리를 절약하기 위해, 각 인덱스 변수는 단지 두 개의 변수로 교체되어야 합니다.

단순화를 위해, 다음 알고리듬 (및 이 기사에서 다른 알고리듬)은 병렬 할당(parallel assignments)을 사용합니다. 이 특색을 가지지 않는 프로그래밍 언어에서, 병렬 할당은 보조 변수로 모의실험되어야 합니다. 예를 들어, 첫 번째 것은,

(old_r, r) := (r, old_r - quotient * r)

다음과 동등합니다:

prov := r;
r := old_r - quotient × prov;
old_r := prov;

그리고 다른 병렬 할당에 대해서도 유사합니다. 이것은 다음 코드로 이어집니다:

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
        (old_t, t) := (t, old_t − quotient × t)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

출력인 최대 공통 약수에 의한 a와 b의 몫은 잘못된 부호를 가질 수 있습니다. 이것은 계산의 끝에서 수정하기 쉽지만 여기서 코드를 단순화하기 위해 수행되지 않았습니다. 마찬가지로, 만약 a 또는 b 중 하나가 영이고 다른 하나가 음수이면, 출력인 최대 공통 약수는 음수이고, 출력의 모든 부호는 변경되어야 합니다.

마지막으로, 베주의 항등식, $ax+by=\gcd(a,b)$ 에서, $a,b,x,\gcd(a,b)$ 가 주어지면 $y$ 에 대해 풀 수 있습니다. 따라서, 위의 알고리듬에 대한 최적화는 $s_{k}$ 수열 (이는 베주 계수 $x$ 를 생성함)만 계산하고, 그런-다음 끝에서 $y$ 를 계산하는 것입니다:

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := (old_r − old_s × a) div b
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

어쨌든, 많은 경우에서 이것은 실제로 최적화가 아닙니다: 이전 알고리듬은 기계 정수 (즉, 자릿수의 고정된 위쪽 경계를 갖는 정수)와 함께 사용될 때, 오버플로에 취약하지 않고, 반면에 bezout_t의 계산에서 old_s * a의 곱셈은 오버플로할 수 있으며, 이 최적화를 최대 크기의 절반 미만으로 표현될 수 있는 입력으로 제한합니다. 무경계진 크기의 정수를 사용할 때, 곱셈과 나눗셈에 필요한 시간은 정수의 크기를 갖는 이차적으로 증가합니다. 이것은 "최적화"가 작은 정수의 곱셈/나눗셈 수열을 단일 곱셈/나눗셈으로 대체한다는 것을 의미하며, 이는 그것이 대체하는 연산을 합친 것보다 더 많은 컴퓨팅 시간이 필요합니다.

Simplification of fractions

분수 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:.0 .1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:.1em .1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0 0,0 0,0 0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}a/b$ 는 만약 $a$ 와 $b$ 가 서로소(coprime)이고 $b$ 가 양수이면 정식의 단순화된 형식입니다. 이 정식의 단순화된 형식은 이전 유사 코드의 세 출력 줄을 다음으로 대체함으로써 얻을 수 있습니다:

if  $s = 0$  then output "Division by zero"
if  $s < 0$  then  $s := - s$ ;   $t := - t$    (for avoiding negative denominators)
if  $s = 1$  then output  $- t$         (for avoiding denominators equal to 1)
output  $- t / s$

이 알고리듬의 증명은 $s$ 와 $t$ 가 $as + bt = 0$ 이고, 따라서 ${\frac {a}{b}}=-{\frac {t}{s}}$ 를 만족하는 두 개의 서로소 정수라는 사실에 의존합니다. 정식의 단순화된 형식을 얻기 위해, 양의 분모를 가지는 것에 대해 빼기 기호를 이동하는 것으로 충분합니다.

만약 $b$ 가 $a$ 를 균등하게 나누면, 알고리듬은 단 한 번의 반복만 실행하고, 알고리듬의 끝에서 $s = 1$ 를 가집니다. 그것은 출력이 정수인 유일한 경우입니다.

Computing multiplicative inverses in modular structures

확장된 유클리드 알고리듬은 모듈러 구조, 전형적으로 모듈러 정수(modular integers)와 대수적 필드 확장(algebraic field extensions)에서 곱셈의 역(multiplicative inverses)을 계산하기 위한 필수 도구입니다. 후자의 경우의 주목할 만한 예제는 비-소수 차수의 유한 필드입니다.

Modular integers

만약 $n$ 이 양의 정수이면, 링 $Z / n Z$ 는 $n$ 에 의한 유클리드 나눗셈(Euclidean division)의 나머지 집합 ${0, 1, ..., n -1}$ , 정수의 덧셈과 곱셈 결과의 나머지를 $n$ 에 의한 나머지로 취하는 것으로 구성하는 덧셈과 곱셈으로 식별될 수 있습니다. $Z / n Z$ 의 원소 $a$ 는 만약 그것이 $n$ 과 서로소이면 곱셈의 역 (즉, 그것은 단위임)을 가집니다. 특히, 만약 $n$ 이 소수이면, $a$ 는 만약 그것이 0 (모듈로 n)이 아니면 곱셈의 역을 가집니다. 따라서 $Z / n Z$ 이 필드인 것과 $n$ 이 소수인 것은 필요충분 조건입니다.

베주의 항등식은 $a$ 와 $n$ 이 서로소인 것과 다음임을 만족하는 정수 $s$ 와 $t$ 가 존재하는 것은 필요충분 조건임을 주장합니다:

ns+at=1

이 항등식 모듈로 $n$ 을 줄이는 것은 다음을 제공합니다:

at\equiv 1\mod n.

따라서 $t$ , 또는, 더 정확하게, $t$ 를 $n$ 으로 나눈 나머지는 $a$ 모듈로 $n$ 의 곱셈의 역입니다.

확장된 유클리드 알고리듬을 이 문제에 적용하기 위해, $n$ 의 베주 계수가 필요하지 않고, 따라서 계산될 필요가 없다는 점에 주목해야 합니다. 역시, 양수이고 n보다 낮은 결과를 얻기 위해, 알고리듬에 의해 제공되는 정수 $t$ 가 $| t | < n$ 를 만족시킨다는 사실을 사용할 수 있습니다. 즉, 만약 $t < 0$ 이면, 끝에서 그것에 $n$ 을 추가해야 합니다. 그 결과 입력 n이 1보다 큰 정수인 유사 코드가 생성됩니다.

function inverse(a, n)
    t := 0;     newt := 1
    r := n;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (t, newt) := (newt, t − quotient × newt) 
        (r, newr) := (newr, r − quotient × newr)

    if r > 1 then
        return "a is not invertible"
    if t < 0 then
        t := t + n

    return t

Simple algebraic field extensions

확장된 유클리드 알고리듬은 단순 대수적 필드 확장(simple algebraic field extensions)에서 곱셈의 역(multiplicative inverses)을 계산하기 위한 주요 도구이기도 합니다. 암호화(cryptography)와 코딩 이론(coding theory)에서 널리 사용되는 중요한 경우는 비-소수 차수의 유한 필드(finite fields)의 경우입니다. 사실, 만약 $p$ 가 소수이고 $q = p d$ 이면, 차수 $q$ 의 필드는 차수 $d$ 의 기약 다항식(irreducible polynomial)의 근에 의해 생성된 $p$ 원소의 소수 필드(prime field)의 단순 대수적 확장입니다.

차수 $d$ 의 기약 다항식 $p$ 의 근에 의해 생성된, 필드 $K$ 의 단순 대수적 확장 $L$ 은 몫 링(quotient ring) $K[X]/\langle p\rangle$ 으로 식별될 수 있고, 그것의 원소는 $d$ 보다 작은 차수의 다항식과 전단사 대응 관계(bijective correspondence)에 있습니다. $L$ 에서 덧셈은 다항식의 덧셈입니다. $L$ 에서 곱셈은 다항식 곱의 $p$ 에 의한 유클리드 나눗셈(Euclidean division)의 나머지입니다. 따라서, $L$ 에서 산술을 완성하기 위해, 곱셈의 역을 계산하는 방법을 정의하는 것만 남아 있습니다. 이것은 확장된 유클리드 알고리듬에 의해 수행됩니다.

그 알고리듬은 모듈러 곱셈 역을 계산하기 위해 위에서 제공된 것과 매우 유사합니다. 두 가지 주요 차이점이 있습니다: 첫째, 제공되는 베주 계수는 항상 $d$ 보다 작은 차수를 가지기 때문에 마지막이지만 한 줄은 필요하지 않습니다. 둘째, 제공되는 최대 공통 약수는, 입력 다항식이 서로소일 때, $K$ 의 임의의 비-영 원소일 수 있습니다; 따라서 이 베주 계수 (일반적으로 양의 차수의 다항식)는 $K$ 의 이 원소의 역으로 곱해야 합니다. 다음 유사 코드에서, $p$ 는 1보다 큰 차수의 다항식이고, $a$ 는 다항식입니다.

function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Example

예를 들어, 만약 유한 필드 GF(2⁸)를 정의하기 위해 사용되는 다항식이 $p = x 8 + x 4 + x 3 + x + 1$ 이고, $a = x 6 + x 4 + x + 1$ 가 역이 필요한 원소이면, 알고리듬을 수행하는 것은 다음 테이블에 설명된 계산을 초래합니다. 차수 2ⁿ의 필드에서, 필드에서 모든 각 원소 z에 대해 −z = z 및 z + z = 0을 가짐을 상기해 보겠습니다. 1은 GF(2)의 유일한 비-영 원소이므로, 유사 코드의 마지막 줄에서 조정이 필요하지 않습니다.

step	quotient	r, newr	s, news	t, newt
		$p = x 8 + x 4 + x 3 + x + 1$	1	0
		$a = x 6 + x 4 + x + 1$	0	1
1	$x 2 + 1$	$x 2 = p - a (x 2 + 1)$	1	$x 2 + 1 = 0 - 1 \cdot (x 2 + 1)$
2	$x 4 + x 2$	$x + 1 = a - x 2 (x 4 + x 2)$	$x 4 + x 2 = 0 - 1(x 4 + x 2)$	$x 6 + x 2 + 1 = 1 - (x 4 + x 2) (x 2 + 1)$
3	$x + 1$	$1 = x 2 - (x + 1) (x + 1)$	$x 5 + x 4 + x 3 + x 2 +1 = 1 - (x +1)(x 4 + x 2)$	$x 7 + x 6 + x 3 + x = (x 2 + 1) - (x + 1) (x 6 + x 2 + 1)$
4	$x + 1$	$0 = (x + 1) - 1 \times (x + 1)$	$x 6 + x 4 + x + 1 = (x 4 + x 2) - (x +1)(x 5 + x 4 + x 3 + x 2 +1)$

따라서, 그 역은 $x 7 + x 6 + x 3 + x$ 로, 두 원소를 함께 곱하고, 나머지를 결과의 $p$ 로 취함으로써 확인할 수 있습니다.

The case of more than two numbers

두 개보다 많은 숫자의 경우를 반복적으로 처리할 수 있습니다. 먼저 $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ 임을 보여줍니다. 이것을 입증하기 위해, $d=\gcd(a,b,c)$ 라고 놓습니다. gcd의 정의에 의해, $d$ 는 $a$ 와 $b$ 의 약수입니다. 따라서 어떤 $k$ 에 대해 $\gcd(a,b)=kd$ 입니다. 마찬가지로, $d$ 는 $c$ 의 약수이므로 일부 $j$ 에 대해 $c=jd$ 입니다. $u=\gcd(k,j)$ 라고 놓습니다. $u$ , $ud|a,b,c$ 의 구성에 의해, 그러나 $d$ 가 최대 약수이기 때문에 $u$ 는 단위(unit)입니다. 그리고 $ud=\gcd(\gcd(a,b),c)$ 이기 때문에, 그 결과가 입증됩니다.