유클리드 알고리즘

 유클리드 알고리즘은 두 정수의 최대공약수(GCD)를 구하는 방법으로 알고리즘 및 예제로 확인한다.

정리.1

두 정수 a, b ∈ Z , a가  b에 의해 나누었을 때 나머지가 r이라고 한다. (여기서 a ≥ b and 0 ≤ r < b) 최대공약수(GCD)는 나머지 r 값에 의해 정의되는 방법으로 아래와 같이 표현한다. GCD( a, b) = ( b, r )  (여기서 나머지 r 값은 a%b) r값이 0이 될 때까지 반복하면 최종 b값이 최대공약수가 된다. GCD( b, r) = GCD( b, 0) = b

.

유클리드 알고리즘(기본형)

/* 입력값: 양의 정수 a, b     r값이 0이면 최대 공약수를 반환*/ function gcd ( a, b ) {     let s, t;     s= a; t=b;     while ( t > 0 ) {                  let r = s % t;           // s를 t로 나눈 나머지 r, (여기서 0 ≤ r < t )         s = t;           t  = r;     }     return s;               }

 

※ 참고로 나머지 r에 대한 수식을 아래와 같이 나타낸다.

• r = a % b → a mod b = r, ( a = q*b + r,  여기서 q: 몫 )

 

예제1]

GCD( 252, 192 ) = 12 결과 값에 대한 과정을 설명한다. (1) (252, 192 ) = 192*1 + 60 (2) (192,  60 ) =  60*3 + 12 (3) (  60,  12 ) = 12*5 + 0 (4) (  12,   0 ) 결과값 = 12 .

예제 1의 계산과정을 표현은 아래처럼 표현된다.

Figure 1. 유클리드 최대공약수 계산

 

유클리드 알고리즘을 이용한 최대공약수를 구하는 내용을 정리 및 예제를 통해 쉽게 이해할 수 있도록 했습니다. 알고리즘이 단순하지만 매우 효율적이며, 다양한 암호학 및 수학문제 해결에 유용합니다.