확장 유클리드 알고리즘(ExGCD)의 원리와 활용
베주 항등식 (Bézout's Identity)
두 정수 \(a\)와 \(b\)의 최대공약수를 \(d = \gcd(a, b)\)라고 할 때, 다음 방정식을 만족하는 정수 \(x\)와 \(y\)가 반드시 존재합니다.
\[ax + by = d\]
더 일반적으로 방정식 \(ax + by = c\)를 풀고자 할 때, \(c\)가 \(d\)의 배수가 아니라면 이 방정식은 정수 해를 가질 수 없습니다.
확장 유클리드 알고리즘의 유도
유클리 ...
10월 19일 17:51에 게시됨
확장 유클리드 알고리즘과 모듈러 역원의 원리 및 활용
확장 유클리드 알고리즘은 기본적인 최대공약수(GCD) 계산을 넘어, 선형 디오판토스 방정식 \(ax + by = \gcd(a, b)\) 의 정수해를 구하는 데 사용된다. 이는 특히 모듈러 산술에서 역원을 구할 때 핵심적으로 활용되며, 암호학이나 수치 해석 분야에서 중요하게 다뤄진다.
기본 개념 및 작동 원리
유클리드 알고리즘은 두 정수 \(a\)와 \(b\)에 대해 \(\gcd(a, b) = \gcd ...
6월 17일 22:32에 게시됨