이 글은 오일러의 정리(Euler’s theorem)를 빠르게 적용하는 법을 예제 중심으로 정리한 자료입니다. 모듈러 연산에서 큰 거듭제곱을 다룰 때 지수를 줄이는 핵심 아이디어, 오일러 피함수 \(\varphi(n)\) 계산법, 중국인의 나머지 정리(CRT)와의 결합, 그리고 RSA 장난감 예시까지 “시험·코딩 면접·CTF·개발 실무”에서 곧장 써먹을 수 있도록 구성했습니다. 본문은 모두 HTML 코드 형태이며, 실행은 고려하지 않습니다. 오일러의 정리: 정의와 공식 정수 … 더 읽기
오일러의 정리(Euler’s theorem)는 수학과 과학 여러 분야에서 쓰이지만, 여기서는 정수론에서의 오일러의 정리를 다루겠습니다. 이 정리는 모듈러 연산(modular arithmetic)에서 거듭제곱을 단순화하는 중요한 도구로, 암호학(특히 RSA 암호)에서 핵심적으로 활용됩니다. 오일러의 정리 정의 정수 \(n\)과 \(a\)가 서로소(\(\gcd(a,n)=1\))이면, 다음이 성립합니다. \[ a^{\varphi(n)} \equiv 1 \pmod{n} \] 오일러의 정리 원리 오일러의 정리는 페르마의 소정리를 일반화한 것입니다. 페르마의 소정리는 \(n\)이 소수 … 더 읽기