유클리드 확장 알고리즘

암호/기본정리

유클리드 확장 알고리즘

mathjs 2024. 10. 20. 15:28

정수의 집합 Z 에서 만약 n = k*d이면, "정수 d는 정수 n을 나눈다".

그리고 다음과 같이 표시한다. → ( d|n )

▷ 정수 a, b, c, x, y ∈ Z 이면,

a|b, b|c이면 a|c이다. (a는 b를 나누고, b는 c를 나눈면, a는 c를 나눈다)
a|b, a|c이면 a|(b·x + c·y)이다.
p가 소수이고 p|a·b이면 p|a 또는 p|b이다.

정리.1

두 정수 a, b에는 다음과 같은 정수 x, y가 존재한다. (베주 항등식)
gcd(a, b) = a·x + b·y
특히, a와 b가 서로소의 관계이면, 다음과 같은 정수 x, y가 존재한다.
a·x + b·y = 1

유클리드 확장 알고리즘

/*입력값: 양의 정수 a, b
결과값: r = a·x + b·y  ( r은 최대공약수)
만약 rn ≠ 0, 결과값이 0이 될 때까지 아래 구문을 반복한다. */
function extend_Euclid(a, b) {
let r1 = a, r2 = b, x1 = 1, y1 = 0, x2 = 0, y2 = 1 , q=0; // 초기값 설정

// 0값을 나올때까지 각각의 변수에 저장
while (r2 > 0) {
q = Math.floor(r1/r2) // 여기서 q(n) = r1/ r2 (q: 몫)
// a = b*q + r_next 수식에서 a = r1, b = r2 대입
// r_next = r1 - q*r2
// x_next, y_next 동일한 수식 적용
r_next = r1 - q*r2;
x_next = x1 - q*x2;
y_next = y1 - q*y2;

// 다음 순환문에서 x_next, y_next, r_next 계산하기 위해 기존값에 순서대로 저장
x1 = x2;
x2= x_next;

y1 = y2;
y2= y_next;

r1 = r2;
r2= r_next;
}
return {x: x1, y: y1, gcd: r1 };    // 반환값 r = a·x + b·y
}

유클리드 확장알고리즘으로 계산하면 아래와 같이 계산 결과값을 확인 할수 있다. 또한 유클리드 알고리즘(최대공약수)과 비교해 본다.