확장 유클리드 알고리즘

산술과 컴퓨터 프로그래밍에서, 확장된 유클리드 알고리즘은 유클리드 알고리즘의 확장이고, 정수 a와 b의 최대공약수(gcd)에 더하여, 또한 정수 x와 y인 Bézout의 항등수의 계수도 계산한다.

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

이것은 증명 알고리즘입니다.gcd가 이 방정식을 만족시키면서 동시에 입력을 나눌 수 있는 유일한 숫자이기 때문입니다.이를 통해 a와 b의 몫은 거의 추가 비용 없이 최대 공약수로 계산할 수 있습니다.

확장 유클리드 알고리즘은 또한 다항식 최대공약수와 2개의 일변량 다항식의 베주트 동일성의 계수를 계산하는 매우 유사한 알고리즘을 참조한다.

확장 유클리드 알고리즘은 a와 b가 공존할 때 특히 유용합니다.이 경우 x는 모듈로 b의 모듈러 곱셈 역, y는 모듈로 a의 모듈러 곱셈 역이다.마찬가지로, 다항식 확장 유클리드 알고리즘은 대수적 필드 확장, 특히 비소수 차수의 유한 필드에서 곱셈 역수를 계산할 수 있게 한다.따라서 두 확장 유클리드 알고리즘 모두 암호학에서 널리 사용된다.특히 모듈러 곱셈 역의 계산은 RSA 공개키 암호화 방식에서의 키쌍 도출에 필수적인 단계입니다.

묘사

표준 유클리드 알고리즘은 몫이 사용되지 않는 일련의 유클리드 나눗셈에 의해 진행됩니다.남은 것만 보관하고 있습니다.확장 알고리즘의 경우 연속되는 지수를 사용합니다.보다 정확하게 말하면, a와 b를 입력으로 하는 표준 유클리드 알고리즘은 $q_{1},\ldots ,q_{k}$ $r_{0},\ldots ,r_{k+1}$ $q$ k {1}({display $style q_$ ${$ 1})와 $q_{1},\ldots ,q_{k}$ $r$ k + 1({display $style r_0},\$ k $+$ })의 $r_{0},\ldots ,r_{k+1}$ 를 $r_{0},\ldots ,r_{k+1}$ 하는 것으로 구성됩니다 $r_{0},\ldots ,r_{k+1}$

{\displaystyle\leq r_{0}&=a\r_{1}&,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\display 0\leq r_{i+1}<\text }\leq r_{i+1}를 정의합니다.

오른쪽의 부등식이 $r_{i-1}$ - $({$ 및 $r_{i-1}$ $r_{i}.$ . $r_{i}.$ {{ $displaystyle r_{i$ $+$ 1})에서 $q_{i}$ i {\displaystyle $q_{$ $i$ } $r_{i+1}$ $r_{i+1}$ + 1 $({$ r_i $+$ 1})를 $r_{i+1}$ $q_{i}$ 하게 정의하는 것은 유클리드 분할의 주요 특성이다. $}$

1이 $r_{k+1}$ $r_{k+1}$ k + $({$ 에 $r_{{k+1}}$ 도달하면 계산이 정지됩니다.최대공약수는 마지막 0이 아닌 $r_{k}.$ $.\displaystyle r_{k}$ 입니다. $}$

확장 유클리드 알고리즘은 비슷하게 진행되지만, 다음과 같이 두 개의 다른 시퀀스를 추가합니다.

{signed}r_{0}&=a&r_{1}&=b\s_{0}&=0\t_{0}&=0&t_{1}&=1\,\vdots &,\r_{0}&,\,\,\vdots\r_{1+i}&{0}&i}&{0}&\\s}}}\s_{i+1}&=s_{i-1}-q_{i}s_{i}&=t_{i-1}-q_{i}t_{i}\&,\vdots\end{aligned}

$r_{k+1}=0$ r $r_{k+1}=0$ k + $r_{k+1}=0$ $=$ (\ $displaystyle r_{k+1$ }= $0})$ 일 $r_{{k+1}}=0$ 때도 계산이 중지되고 다음과 같이 표시됩니다.

$r_{k}$ k $(\$ 는 $r_{k}$ $a=r_{0}$ $a=r_{0}$ a $a=r_{0}$ 0 $(\$ a $=r_{0})$ $b=r_{1}.$ b $b=r_{1}.$ 1 $(\displaystyle$ b $=r_{1})$ 의 최대 공약수입니다. $}$
Bézout 계수는 s $(\$ }) $t_{k},$ $t_{k},$ k $(\displaystyle t_{k}),$ 즉 $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$ b $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$ $=$ $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$ $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$ + $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$ $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$ k(\ $displaystyle \gcd(a,$ b)= $r_{k$ }= $as_{k}+bt_k})$ 입니다 $t_{k},$ .
a와 b의 몫은 최대 공약수로 s $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ + $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ ± $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ ( $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ , $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ ) $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ \ $pm {\frac$ { $b$ } {\ $gcd$ $(a$ , $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ ) $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ } $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ t $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ + $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ ± $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ gcd ( $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ , $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ b $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$ ) = ${\pm frac$ { frac $}$ = { $displaystyle t_k+1$ \pm $cd$ ( a , b ) } { frcdisplay $styl$ } { $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ } } } }

또한 a와 b가 모두 양의 값이고 $\gcd(a,b)\neq \min(a,b)$ ( $\gcd(a,b)\neq \min(a,b)$ $\gcd(a,b)\neq \min(a,b)$ ) $\gcd(a,b)\neq \min(a,b)$ ( a $\gcd(a,b)\neq \min(a,b)$ , $\gcd(a,b)\neq \min(a,b)$ $){$ $displaystyle$ \ $gcd (a ,$ b $)\neq \min$ ( a , $b$ ) $\gcd(a,b)\neq \min(a,b)$ 인 경우,

\displaystyle s_{i} \left\lfloor \frac {b} {2\gcd(a,b)} \right\loor \left\lfloor \left\lfloor \frac {a} {2\gcd(a,b)} \right\loor \loor \floor \floor \floor \floor \frac {2\floor }

$0\leq i\leq k,$ i $0\leq i\leq k,$ k $0\leq i\leq k,$ 、 { $style$ 0 \ $leq$ i \ $leq$ k $}$ $\lfloor x\rfloor$ 여기서 $\lfloor x\rfloor$ " $x"$ 는 x의 $정수$ 부분, 즉 x보다 $크지$ 않은 최대 정수입니다.

이것은 확장 유클리드 알고리즘에 의해 제공된 베주트 계수의 쌍이 위의 부등식을 모두 만족시키는 유일한 쌍으로서 베주트 계수의 최소 쌍임을 암시한다.

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

예

다음 표는 확장 유클리드 알고리즘이 입력 240과 46으로 어떻게 진행되는지 보여줍니다.최대공약수는 0이 아닌 마지막 항목인 "remainder" 열의 2입니다.나머지 행이 0이므로 6행에서 계산이 중지됩니다. 두 번째에서 마지막 행의 마지막 두 개 항목에 Bézout 계수가 표시됩니다.실제로 -9 × 240 + 47 × 46 = 2. 마지막으로 마지막 행의 마지막 두 항목 23과 -120이 최대 공약수 2에 의해 입력 46과 240의 몫임을 쉽게 확인할 수 있다.

인덱스 i	지수_i−1 Q	나머지_i r	s_i	t_i
0		240	1	0
1		46	0	1
2	240 ÷ 4646 = 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

증명

$r_{i}$ $0\leq r_{i+1}<|r_{i}|,$ $0\leq r_{i+1}<|r_{i}|,$ + $0\leq r_{i+1}<|r_{i}|,$ < $0\leq r_{i+1}<|r_{i}|,$ , { $displaystyle$ 0 \ $leq r$ $_$ { $i$ + $1$ } < $r$ _ { $i }$ $0\leq r_{i+1}<|r_{i}|,$ $r_{i}$ 0 、 r $_$ { $i$ }의 $0\leq r_{i+1}<|r_{i}|,$ $r_{i}$ 순서는 음이 아닌 정수(i = 2부터)의 내림차순서입니다.따라서 $r_{k+1}=0.$ $r_{k+1}=0.$ + 1 $=$ 0으로 정지해야 $합니다.$ {\ $displaystyle r_{k+$ 1}= $0$ } 이것은 $r_{k+1}=0.$ 알고리즘이 최종적으로 정지하는 것을 증명합니다 $.$

$(r_{i-1},r_{i})$ $r_{i+1}=r_{i-1}-r_{i}q_{i},$ i + $r_{i+1}=r_{i-1}-r_{i}q_{i},$ $r_{i+1}=r_{i-1}-r_{i}q_{i},$ $r_{i+1}=r_{i-1}-r_{i}q_{i},$ - $r_{i+1}=r_{i-1}-r_{i}q_{i},$ - r $r_{i+1}=r_{i-1}-r_{i}q_{i},$ $r_{i+1}=r_{i-1}-r_{i}q_{i},$ i $r_{i+1}=r_{i-1}-r_{i}q_{i},$ , { $display$ $style$ $r$ _ { $i$ + $1$ $(r_{i-1},r_{i})$ } = $r$ _ { i $}-r$ $(r_{i-1},r_{i})$ { $i$ $(r_{i-1},r_{i})$ } $q$ _ { i $}$ $(r_{i-1},r_{i})$ displaydisplay $(r_{i},r_{i+1}).$ 、 $(r_{i},r_{i+1}).$ style ( $r$ _ { i - $(r_{i-1},r_{i})$ , $(r_{i},r_{i+1}).$ $(r_{i-1},r_{i})$ _ $1$ ) $및$ r + r $(r_{i},r_{i+1}).$ ) $、$ $}$ 입력 $(r_{i},r_{i+1}).$ $a=r_{0},b=r_{1}$ = $a=r_{0},b=r_{1}$ 0 , b $a=r_{0},b=r_{1}$ = $a=r_{0},b=r_{1}$ 1 ({ $displaystyle a$ = r_{ $0}$ , $b = r_{$ 1 $a=r_{0},b=r_{1}$ } )의 $r_{k},r_{k+1}=0.$ 는 $r_{k},r_{k+1}=0.$ $r_{k},r_{k+1}=0.$ + $r_{k},r_{k+1}=0.$ = $r_{k},r_{k+1}=0.$ { $displaystyle r_{k$ } , $r_{k+1$ } $=$ 0.} 이는 $r_{k},r_{k+1}=0.$ r $r_{k}$ (\ $displaystyle r_{$ k $r_{k}$ })가 a와 b의 최대공약수임을 $r_{k}$ 한다 $.($ 이 시점까지 증명은 기존의 유클리드 알고리즘과 동일)

a $a=r_{0}$ $a=r_{0}$ $({$ a $=r_{0})$ $b=r_{1},$ b $b=r_{1},$ $({displaystyle b=r_{$ 1})로서 $b=r_{1},$ i = 0 및 1에 대해 $as_{i}+bt_{i}=r_{i}$ + $as_{i}+bt_{i}=r_{i}$ $as_{i}+bt_{i}=r_{i}$ $=$ $as_{i}+bt_{i}=r_{i}$ $({$ }= $r_{i})$ 가 $as_{i}+bt_{i}=r_{i}$ $as_{i}+bt_{i}=r_{i}$ .이 관계는 모든 $i>1$ > $i>1$ { $displaystyle i$ 1 에 대해 유도됩니다.

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

$s_{k}$ s k $(\$ }) $t_{k}$ t $(\$ 는 $t_{k}$ Bézout 계수입니다.

매트릭스를 고려하다

({displaystyle A_{i}=s_{i-1}&s_{i}\t_{i}\end{pmatrix})}

반복 관계는 매트릭스 형태로 다시 작성될 수 있습니다.

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

$A_{1}$ A $({$ 은 $A_{1}$ 항등 행렬이며 행렬식은 1입니다.위의 공식에서 가장 오른쪽 행렬의 행렬식은 -1이다.따라서 $(\$ })의 $A_{i}$ $(-1)^{{i-1}}.$ 행렬식은 $(-1)^{i-1}.$ (- $(-1)^{i-1}.$ - $(-1)^{i-1}.$ . { $displaystyle$ (- $1)^{i-1}$ 입니다. $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ $i=k+1,$ $i=k+1,$ $i=k+1,$ + $i=k+1,$ 1 $i=k+1,$ , { $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ i $= k$ $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ + $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ ( $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ - $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ ) k $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ $s_k$ { $k$ } 입니다 $i=k+1,$ $.$ identity는 s $s_{k+1}$ + $s_{k+1}$ ({ $display$ style $s_{k+1})$ 과 $s_{k+1}$ t $t_{k+1}$ + $t_{k+1}$ ({ $displaystyle t_{k+1})$ 이 $t_{k+1}$ 동일하다는 것을 $s_{k+1}$ . $as_{k+1}+bt_{k+1}=0$ 에서 증명된 $as_{k+1}+bt_{k+1}=0$ $as_{k+1}+bt_{k+1}=0$ + $as_{k+1}+bt_{k+1}=0$ + $as_{k+1}+bt_{k+1}=0$ $as_{k+1}+bt_{k+1}=0$ + $as_{k+1}+bt_{k+1}=0$ $=$ { $displaystyle as$ _ { $k+1}$ + $bt_{k+1$ }= $0}$ 의 $as_{{k+1}}+bt_{{k+1}}=0$ 관계는 s k + $s_{k+1}$ 1 { $displaystyle s_{$ $k+$ $1}}$ 의 $s_{k+1}$ $s_{k+1}$ 를 $나눈다는$ 것을 $b=ds_{k+1}$ , 즉 일부 d1의 $b=ds_{k+1}$ $b=ds_{k+1}$ 정수에 $대해$ b $=$ $b=ds_{k+1}$ + $b=ds_{k+1}$ { $styleds_ds}$ 이다. $as_{k+1}+bt_{k+1}=0$ $s_{k+1}$ k + $({$ 로 $s_{k+1}$ 나누면 s $as_{k+1}+bt_{k+1}=0$ + $as_{k+1}+bt_{k+1}=0$ + $as_{k+1}+bt_{k+1}=0$ $as_{k+1}+bt_{k+1}=0$ + 1 $=$ ({ $displaystyle as_{k+1}+0})$ 의 $as_{{k+1}}+bt_{{k+1}}=0$ 관계는 $=$ - $a=-dt_{k+1}.$ $a=-dt_{k+1}.$ + $a=-dt_{k+1}.$ 1이 $.$ { $displaystyle$ a=- $dt_{k+$ }} $s_{k+1}$ 즉 $a=-dt_{k+1}.$ $,$ $s_{k+1}$ k + 1({ $style s_{$ k $s_{k+1}$ +1 $-t_{k+1}$ 과 $-t_{k+1}$ k $-t_{k+1}$ + 1({ $displaystyle -t_{k+$ 1 $-t_{k+1}$ })은 공통 인수에 $의한$ a와 b의 $몫$ 인 공유 정수이며, 따라서 이들의 최대 공약수 또는 그 반대이다 $.$

, a와 b와(a, b)≠분(a, b){\displaystyle \gcd(a,b)\neq \min(a,b)}gcd 긍정적인 있다고 추측한다. 그리고 ≠ b{a\neq b\displaystyle}은<>b{\displaystyle a<, b},(a,b)의 EEA에 s, 그리고 밀폐된 시퀀스다, 초기 0과 1초, 그 밀폐되는 것을 볼 수 있고 마지막 주장을 입증하려면. ssequ(b,a)에 대해 입력한다.정의에서는 (a,b) 케이스가 (b,a) 케이스로 감소하는 것을 나타냅니다.따라서 a $a>b$ > $a>b$ { $displaystyle$ a > $b$ }가 $a>b$ 일반성을 잃지 않는다고 가정합니다.

$s_{2}$ 2 $({$ 는 $s_{2}$ $s_{3}$ 이고 s $({$ $\gcd(a,b)\neq \min(a,b)$ $\gcd(a,b)\neq \min(a,b)$ $\gcd(a,b)\neq \min(a,b)$ b ) $\gcd(a,b)\neq \min(a,b)$ ( $\gcd(a,b)\neq \min(a,b)$ , $\gcd(a,b)\neq \min(a,b)$ , $b$ )\ $neq \min (a , b$ ) $\gcd(a,b)\neq \min(a,b)$ )는 음의 정수임을 알 수 있습니다.그 후는 나는}{\displaystyle s_{나는}alternate 로그인과 양에서 귀납적으로 정의에서, q 나는 ≥ 11}나는 k{1\leq i\leq k\displaystyle}≤ 1≤에, 나는 1{\displaystyle i=1} 일고 있는듯이{\displaystyle q_{나는}\geq기 때문에 a>b{\di 다음과 같이 엄격하게 증가한다.sp $laystyle a >$ b $a>b$ 。같은 이유로 처음 몇 개의 용어 이후의 $($ 도 $t_{i}$ 마찬가지입니다.또한 $q_{k}\geq 2$ k $2$ 2 $($ a와 b가 모두 양의 경우 및 $\gcd(a,b)\neq \min(a,b)$ ) $\gcd(a,b)\neq \min(a,b)$ min ( $a$ b $)\neq$ \min (a, b) $\gcd(a,b)\neq \min(a,b)$ ） a 2 （ displaystyle $\gcd (a, b)$ \ $neq \min$ ( $a,$ b) $}$ 따라서,

({displaystyle 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 s_k{k}}}}.k}.k}.k}:

이는 s $s_{k},t_{k}$ $s_{k},t_{k}$ k $(\$ }, $t_{k})$ 의 $s_{k},t_{k}$ 절대값이 각각 $s_{i}$ 의 s $s_{i}$ (\ $displaystyle s_{$ i $s_{i}$ }) $t_{i}$ t i(\ $displaystyle t_{$ i $t_{i}$ })보다 크거나 같다는 $s_{k},t_{k}$ 을 수반한다.

다항식 확장 유클리드 알고리즘

한 장의 계수를 갖는 일변량 다항식의 경우, 유클리드 나눗셈, 베주트의 항등식 및 확장 유클리드 알고리즘 등 모든 것이 비슷하게 작용한다.첫 번째 차이점은 유클리드 나눗셈과 알고리즘에서 $0\leq r_{i+1}<|r_{i}|$ 0 $0\leq r_{i+1}<|r_{i}|$ $0\leq r_{i+1}<|r_{i}|$ + $0\leq r_{i+1}<|r_{i}|$ 1 < $0\leq r_{i+1}<|r_{i}|$ \ $displaystyle$ 0 \ $leq r _$ { $i$ + $1$ } < r _ { $\deg r_{i+1}<\deg r_{i}.$ $0\leq r_{i+1}<|r_{i}|$ $\deg r_{i+1}<\deg r_{i}.$ 는 $0\leq r_{{i+1}}<|r_{i}|$ deg $\deg r_{i+1}<\deg r_{i}.$ . { $displaystyle \deq$ r $_ 1$ $}도에서의$ 부등식으로 대체해야 한다는 것입니다.} 그렇지 $\deg r_{i+1}<\deg r_{i}.$ 않으면, 이 기사에서 앞에 나오는 모든 것은 정수를 다항식으로 대체하는 것만으로 동일하게 유지됩니다 $.$

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

만약 a와 b가 두 개의 0이 아닌 다항식이라면, 확장 유클리드 알고리즘은 다음과 같은 독특한 다항식 쌍 (s, t)을 생성한다.

as+bt=\gcd(a,b)

그리고.

\displaystyle \displays b-\displays(\gcd(a,b),\displays \displays a-\displays(\gcd(a,b)),\displays \displays t(\gcd(a,b)).}

세 번째 차이점은 다항식의 경우 최대공약수는 0이 아닌 상수에 의한 곱셈까지만 정의된다는 것입니다.가장 큰 공약수를 명확하게 정의할 수 있는 몇 가지 방법이 있습니다.

수학에서, 최대공약수는 단수 다항식이어야 하는 것이 일반적이다.이를 얻으려면 출력의 모든 요소를 $r_{k}.$ k $.\displaystyle r_{k}$ 의 $r_{k}.$ 계수로 나누면 됩니다.} a와 $r_{{k}}.$ b가 공수일 경우, 베주 부등식의 오른쪽에서 1을 얻을 수 있습니다 $.$ 그렇지 않으면 0이 아닌 상수를 얻을 수 있습니다.컴퓨터 대수학에서, 다항식은 일반적으로 정수 계수를 가지며, 최대공약수를 정규화하는 이 방법은 너무 많은 분수를 도입하여 편리하지 않다.

정수 계수를 갖는 다항식의 경우 최대공약수를 정규화하는 두 번째 방법은 모든 출력을 r $,\displaystyle r_{k}$ 의 $r_{{k}},$ $r_{k},$ 으로 나누어 원시 최대공약수를 얻는 것입니다.입력 다항식이 공수인 경우, 이 정규화는 1과 같은 최대 공약수를 제공합니다.이 접근법의 단점은 계산 중에 많은 분수를 계산하고 단순화해야 한다는 것이다.

세 번째 접근법은 확장된 유클리드 알고리즘에 대한 유클리드 알고리즘의 확장과 유사한 방식으로 하위 결과 유사 잔량 시퀀스의 알고리즘을 확장하는 것으로 구성된다.따라서 정수 계수를 갖는 다항식으로 시작할 때 계산되는 모든 다항식이 정수 계수를 가질 수 있습니다.또한 계산된 모든 $r_{i}$ $(\$ })는 $r_{i}$ 하위 결과 다항식이다.특히, 만약 입력 다항식이 공수라면, 베주트의 항등식은

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

$\operatorname {Res} (a,b)$ $\operatorname {Res} (a,b)$ ( $\operatorname {Res} (a,b)$ , $\operatorname {Res} (a,b)$ ) { $displaystyle \operatorname {Res$ } ( $a$ , $b$ )는 $\operatorname {Res} (a,b)$ a 와 b 의 결과를 나타냅니다.이런 형태의 베주우 정체성에서는 공식에 분모가 없다.만약 모든 것을 결과로 나눈다면, 그 안에 나타나는 유리수에 대한 명확한 공통 분모와 함께 고전적인 베주우(Bézou)의 동일성을 얻게 된다.

유사 코드

위에서 설명한 알고리즘을 구현하려면 먼저 각 단계에서 필요한 것은 인덱스 변수의 마지막 두 값뿐이라는 점을 지적해야 합니다.따라서 메모리를 절약하기 위해 각 인덱스 변수는 2개의 변수만으로 대체해야 합니다.

알기 쉽게 하기 위해 다음 알고리즘(및 이 문서의 다른 알고리즘)에서는 병렬 할당을 사용합니다.이 기능이 없는 프로그래밍 언어에서는 보조 변수를 사용하여 병렬 할당을 시뮬레이션해야 합니다.예를 들어, 첫 번째는

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

와 동등하다

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

다른 병렬 할당도 마찬가지입니다.이로 인해 다음과 같은 코드가 생성됩니다.

함수 extended_gcd(a, b)(old_r, r) := (a, b)(old_s, s) := (1, 0)(old_t, t) := (0, 1) 반면 r do 0 do extended_r div r (old_r, r) := (r, old_r - 、 s : s ) :old_t) 출력 "공약수:", old_r 출력 "gcd:의 성분", (t, s)

a와 b의 최대공약수(출력)의 몫에 잘못된 부호가 있을 수 있습니다.이것은 계산의 마지막에 수정하는 것은 간단하지만, 코드 심플화를 위해서 여기에서는 행해지지 않았습니다.마찬가지로 a 또는 b 중 하나가 0이고 다른 하나가 음수일 경우 출력되는 최대공약수는 음수이므로 출력의 모든 부호를 변경해야 합니다.

$ax+by=\gcd(a,b)$ 으로 b $a,b,x,\gcd(a,b)$ b, x, gcd ( $a,b,x,\gcd(a,b)$ $ax+by=\gcd(a,b)$ b $)$ (a, $ax+by=\gcd(a,b)$ ({ $ax+by=\gcd(a,b)$ $ax$ + $by$ $=\gcd$ $a,b,x,\gcd(a,b)$ $a, b$ ( $a,b,x,\gcd(a,b)$ $)$ { $displaystyle$ a $, b}$ ( $a$ , b) { $displaystyle$ a $a,b,x,\gcd(a,b)$ $x, gcd(a, b$ 에 대해 $a,b,x,\gcd(a,b)$ 할 수 있는 $ax+by=\gcd(a,b)$ x + $by$ (a, gcd(a, b)는 알고리즘입니다.는 Bézout $계수$ x(\ $displaystyle$ x)를 산출하고 마지막에 y $(\displaystyle$ y $)$ 를 $y$ $y$ 합니다.

함수 extended_gcd(a, b) s := 0; old_s := 1 r := b; old_r := a while r r 0 do quotient := (r, old_r - quotient × r) := (r, s) : old_r - s - quotient × r ( b ) : out bes _ bez_ bez bez bez bez b then then 0 、 b _ out 。ut "베주트 계수:", (old_s, bezout_t) 출력 "가장 큰 공통수:", old_r

그러나 대부분의 경우 이것은 실제로 최적화가 아닙니다.전자의 알고리즘은 기계 정수(즉, 고정된 자릿수의 상한을 가진 정수)와 함께 사용했을 때 오버플로우되기 쉬운 반면, bezout_t의 계산에서 old_s * a의 곱셈은 오버플로우 될 수 있으며, 이 최적화는 보다 적은 값으로 표현될 수 있는 입력으로 제한될 수 있습니다.최대 크기의 절반보다 더 커요.크기가 무제한인 정수를 사용하는 경우 곱셈과 나눗셈에 필요한 시간은 정수의 크기에 따라 2차적으로 증가합니다.이는 "최적화"가 작은 정수의 곱셈/나눗셈 시퀀스를 단일 곱셈/나눗셈으로 대체한다는 것을 의미하며, 이를 대체한 연산보다 더 많은 연산 시간을 필요로 한다.

분수의 단순화

한 분파.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac.num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1pxsolid}.mw.만약 a와 b다 coprime와 b는 긍정적 -parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}a/b 정준 약식이다.이 표준적인 단순화된 형식은 앞의 의사 코드의 3개의 출력 라인을 다음과 같이 치환함으로써 얻을 수 있습니다.

 $s$  =  $0$ 이면 "0으로 나눗셈"을 출력하고, $s$  = 1이면 "0으로 나눗셈"을 출력한 다음, s :=  $-s$ (음수 분모를 피하기 위해) t를  $출력$ 합니다 $.$

이 알고리즘의 증명은 $s$ 와 $t$ 가 + bt = 0과 ${\frac {a}{b}}=-{\frac {t}{s}}$ $두$ 개의 공칭 정수라는 $사실$ 에 의존하며, ${\frac {a}{b}}=-{\frac {t}{s}}$ ${\frac {a}{b}}=-{\frac {t}{s}}$ ${\frac {a}{b}}=-{\frac {t}{s}}$ - ${\frac {a}{b}}=-{\frac {t}{s}}$ \ $displaystyle$ \ $frac$ { $a$ } = - { \ $frac$ { $t$ } { $s$ } ${\frac {a}{b}}=-{\frac {t}{s}}$ } 。정규적인 단순화된 형식을 얻으려면 양의 분모를 갖는 음수 부호를 이동하면 충분하다.

$b$ 가 a를 균등하게 $나누면$ 알고리즘은 1회만 반복 실행되며 알고리즘 끝에 s = $1$ 이 $있습니다$ .출력이 정수인 유일한 경우입니다.

모듈러 구조의 곱셈 역계산

확장 유클리드 알고리즘은 모듈러 구조, 전형적으로 모듈러 정수와 대수적 필드 확장을 곱셈 반전을 계산하는 데 필수적인 도구이다.후자의 경우에서 주목할 만한 예는 비프라임 순서의 유한 필드입니다.

모듈러 정수

n이 양의 정수일 $경우$ , 링 $Z / nZ$ 는 유클리드 나눗셈의 나머지 $n$ 의집합 { $0,$ 1, $..., n-1}$ 에 의해 동정될 수 있다.Z $/ nZ$ 의 $원소$ a는 $n$ 과 공역하면 곱셈역(즉 단위)을 가진다.특히 n이 소수일 $경우$ $a$ 는 0이 아니면 곱셈 역수를 갖는다( $modulo$ n). $따라서$ Z $/ nZ$ 는 n이 소수인 $경우$ 에만 필드입니다.

베주트의 정체성은 다음과 같은 $정수$ $s$ 와 t가 존재하는 경우에만 $a$ 와 n은 공수라고 $주장$ 한다.

ns+at=1

이 아이덴티티 $모듈$ 을 줄이면

(\explaystyle at\equiv 1\mod n.)

$따라서$ t, 또는 더 정확히는 $t$ 를 $n$ 으로 나눈 나머지가 $모듈$ 로 $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

단순 대수적 필드 확장

확장 유클리드 알고리즘은 또한 단순한 대수적 필드 확장에서 곱셈 역수를 계산하기 위한 주요 도구이다.암호학 및 부호화 이론에서 널리 사용되는 중요한 사례는 유한한 비프라임 순서 분야이다.사실, p가 $소수$ 이고 $q d$ = $p$ 라면, $순서장$ q는 p $원소$ 의 소수장의 단순한 대수적 확장이며, $차수$ d의 환원 불가능한 다항식의 근에 의해 생성된다.

$K[X]/\langle p\rangle ,$ K [ $K[X]/\langle p\rangle ,$ ] / $K[X]/\langle p\rangle ,$ p $K[X]/\langle p\rangle ,$ δ $,$ \ $displaystyle$ K [ $X$ ] / \ $langle$ p \ $rangle$ , $K[X]/\langle p\rangle ,$ 에 $대해$ d $미만$ 의 $다항식$ 에 대응하는 필드 $K$ 의 단순 대수적 $확장$ L을 동정할 수 있다. $L$ 의 덧셈은 다항식의 덧셈이다. $L$ 에서의 곱은 다항식의 곱에 대한 $p$ 로 유클리드 나눗셈의 나머지다.따라서 L에서 $산술$ 을 완료하려면 곱셈 역수를 계산하는 방법만 정의하면 됩니다.이것은 확장 유클리드 알고리즘에 의해 이루어집니다.

이 알고리즘은 모듈러 곱셈 역수를 계산하기 위해 위에서 설명한 것과 매우 유사합니다.두 가지 주요 차이점이 있습니다.첫 번째는 마지막 라인이 필요 없습니다.이는 제공된 베주 계수가 항상 $d$ 보다 작기 때문입니다.둘째, 입력 다항식이 공수일 때 제공되는 최대공약수는 $K$ 의 0이 아닌 원소가 될 수 있다. 따라서 이 베주 계수(일반적으로 양의 정도의 다항식)에 $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

예

예를 들어, 유한장 GF⁸(2)를 정의하는 데 사용되는 다항식이 p⁸ = x⁴ + x³ + x + x + 1이고 a⁶ = x + x⁴ + x + 1이 역수인 경우, 알고리즘을 수행하면 다음 표에 설명된 계산이 됩니다.순서ⁿ 2의 필드에는 필드의 모든 요소 z에 대해 -z = z 및 z + z = 0)이 있습니다.1은 GF(2)의 유일한 비제로 요소이기 때문에 의사 코드의 마지막 행에서의 조정은 필요하지 않습니다.

걸음	몫의	r, newr	s, 뉴스	t, newt
		p = x⁸ + x⁴³ + x + x + 1	1	0
		a = x⁶ + x⁴ + x + 1	0	1
1	x² + 1	x² = p - a (x² + 1)	1	x² + 1 = 0 - 1 × (x² + 1)
2	x⁴ + x²	x + 1 = a - x² (x⁴ + x² )	x⁴+x² = 0 - 1 (x⁴+x²)	x⁶ + x² + 1 = 1 - (x⁴ + x² ) (x² + 1)
3	x + 1	1 = x² - (x + 1) (x + 1)	x⁵+x⁴+x³²+1 = 1 - (x + 1) (x⁴ + x² )	x⁷⁶ + x³ + x + x = (x² + 1) - (x + 1) (x⁶ + x² + 1)
4	x + 1	0 = (x + 1) - 1 × (x + 1)	x⁶ + x⁴ + x + 1 = (x⁴+x²) - (x+1) (x⁵+x⁴³+x²+1)

따라서 역수는 x + x⁶ + x³ + x + x 입니다⁷.이것은 두 요소를 함께 곱하고 나머지를 결과의 $p$ 로 구함으로써 확인할 수 있습니다.

번호가 3개 이상인 경우

3개 이상의 숫자를 반복하여 처리할 수 있습니다.먼저 $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ ( $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ , $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ , $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ ) $=$ $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ , $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ ) , $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ ) { $displaystyle \gcd ( a$ , $b$ , c ) $=\gcd$ ( \ $gcd ( a$ , b , $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ c ) $d=\gcd(a,b,c)$ 。 $이$ 를 $d=\gcd(a,b,c)$ 하려면 d $d=\gcd(a,b,c)$ $d=\gcd(a,b,c)$ $d=\gcd(a,b,c)$ , $d=\gcd(a,b,c)$ , $d=\gcd(a,b,c)$ ) { $displaystyled$ ( $a$ , $b$ , c ) = $gcd$ ( a , $cd$ ) $d=\gcd(a,b,c)$ 、 cd ( cd ) } $d=\gcd(a,b,c)$ } 。 $gcd$ $\gcd(a,b)=kd$ ( $\gcd(a,b)=kd$ , $\gcd(a,b)=kd$ ) $\gcd(a,b)=kd$ $\gcd(a,b)=kd$ $displaystyle$ $\gcd$ ( $a$ , $u=\gcd(k,j)$ ) $u=\gcd(k,j)$ $= kd$ 。 $d$ 로 $displaystyle$ d는 $d$ $c$ 의 $c$ 약수이므로 $c=jd$ $c=jd$ $j$ $c=jd$ $displaystyle$ $c=$ jd $c=jd$ $j$ $u$ cd ( $display$ style $k$ k $u=\gcd(k,j)$ ) $u=\gcd(k,j)$ kdisplay $=$ kdisplay style = $u=\gcd(k,j)$ . $u$ \ $displaystyle$ $ud|a,b,c$ $u$ , $ud|a,b,c$ d $ud|a,b,c$ , $ud|a,b,c$ , $ud|a,b,c$ \ $displaystyle ud$ a $, b$ , $c$ \ $displaystyle$ d는 최대 $d$ $약수$ 이므로 $u$ $u$ 는 단위입니다.그리고 $ud=\gcd(\gcd(a,b),c)$ d $ud=\gcd(\gcd(a,b),c)$ $ud=\gcd(\gcd(a,b),c)$ $ud=\gcd(\gcd(a,b),c)$ ( $ud=\gcd(\gcd(a,b),c)$ a $ud=\gcd(\gcd(a,b),c)$ , $ud=\gcd(\gcd(a,b),c)$ ) , $ud=\gcd(\gcd(a,b),c)$ c ) { $displaystyle$ ud = \ $gcd$ ( \ $gcd ( a$ , $b$ ) $ud=\gcd(\gcd(a,b),c)$ } $ud=\gcd(\gcd(a,b),c)$ u is is is u is is and is is is is is is is is is is is is is and and and and and and and

$na+mb=\gcd(a,b)$ n a $na+mb=\gcd(a,b)$ + $na+mb=\gcd(a,b)$ b $na+mb=\gcd(a,b)$ $na+mb=\gcd(a,b)$ $na+mb=\gcd(a,b)$ , $na+mb=\gcd(a,b)$ $){$ $displaystyle$ na + $mb$ = \ $gcd$ $($ $a$ , $b$ $x\gcd(a,b)+yc=\gcd(a,b,c)$ ) + $y$ c $=$ $x\gcd(a,b)+yc=\gcd(a,b,c)$ ( $x\gcd(a,b)+yc=\gcd(a,b,c)$ , $x\gcd(a,b)+yc=\gcd(a,b,c)$ , $c ){ displaystyle$ x $x\gcd(a,b)+yc=\gcd(a,b,c)$ } $x\gcd(a,b)+yc=\gcd(a,b,c)$ y { $displaystyle$ y $}$ 가 $y$ $.$

({displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c)},

그래서 n개의 숫자에 적용하기 위해 우리는 유도를 사용한다.

\displaystyle \gcd(a_{1},a_{n})=\gcd(a_{1},\gcd(a_{2},\gcd(a_{3},\gcd,\gcd(a_{n1},a_{n}),\gcd,\gcd(a_{n})},\gcdisplaystyland(a_{n}),

방정식이 직접 뒤따르는 거죠.

「」를 참조해 주세요.

레퍼런스

Knuth, Donald. The Art of Computer Programming. Addison-Wesley. 제2권 제4장
토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7.섹션 31.2의 859-861 페이지: 최대 공약수.

외부 링크

GF(2^8)의 곱셈 역수를 결정하기 위해 사용되는 알고리즘 형식의 소스

v t 수이론 알고리즘
프라이머리 테스트	AKS APR 빌리전원 소프트웨어 타원 곡선 포클링턴 페르마 루카스 루카스-레머 루카스-레머-리젤 프로스의 정리 페핀스 이차 프로베니우스 솔로베이-스트라센 밀러-라빈
소생성	앳킨의 체 에라토스테네스의 체 프리차드의 체 순다람의 체 휠 인수분해
정수 인수분해	연속분율(CFRAC) 딕슨스 렌스트라 타원 곡선(ECM) 오일러의 폴라드 로 p − 1 p + 1 2차 체(QS) 일반 번호 필드 체(GNFS) 특수 번호 필드 체(SNFS) 유리 체 페르마의 샹크스의 정사각형 형태 트라이얼 부문 쇼르스
곱셈	고대 이집트인 긴 카라츠바 툼쿡 쇠나게슈트라센 훼러스
유클리드 나누기	바이너리 청킹 푸리에 골드슈미트 뉴턴 라프슨 긴 짧다 SRT
이산 로그	베이비 스텝 거인 스텝 폴라드 로 폴라드캥거루 폴리그-헬만 지수 미적분 함수 필드 체
최대 공약수	바이너리 유클리드 확장 유클리드 레머즈
모듈러 제곱근	시폴라 포클링턴스 토넬리 생크스 베를레캄프 쿠네스
기타 알고리즘	차크라발라 코르나키아 제곱에 의한 지수화 정수 제곱근 정수 관계(LL; KZ) 모듈러형 지수화 몽고메리 환원 스쿠프 트라크텐베르크 시스템
이탤릭체는 특수 형식의 숫자에 대한 알고리즘임을 나타냅니다.

Search

확장 유클리드 알고리즘

네임스페이스

더

목차

묘사

예

증명

다항식 확장 유클리드 알고리즘

유사 코드

분수의 단순화

모듈러 구조의 곱셈 역계산

모듈러 정수

단순 대수적 필드 확장

예

번호가 3개 이상인 경우

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

확장 유클리드 알고리즘

묘사

예

증명

다항식 확장 유클리드 알고리즘

유사 코드

분수의 단순화

모듈러 구조의 곱셈 역계산

모듈러 정수

단순 대수적 필드 확장

예

번호가 3개 이상인 경우

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.