유클리드 알고리즘 유클리드 알고리즘은 유클리드 호제법이라고 불리며 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이라는 말은 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 의미한다. 유클리드 알고리즘은 RSA 암호화 기법에 사용된다. 원리 예시) 78696과 19332의 최대공약수를 구하면, gcd(78696, 19332) 78696 ＝19332×4 ＋ 1368 gcd(19332, 1368) 19332 ＝ 1368×14 ＋ 180 gcd(1368, 180) 1368 ＝ 180×7 ＋ 108 gcd(180, 108) 180 ＝ 108×1 + 72 gcd(108, 72) 108 ＝ 72×1 ＋ 36 gcd(72, 36) 72 ＝36×2 + 0 gcd(36, 0) 즉, g..