합동식, 오일러(Euler)함수 [Crypto]
· 합동식 - a 와 b 는 mod m 상에서 합동이다 → a ≡ b mod m ex) mod 7 상에서 5와 합동인 수를 모두 쓰면? → [5, 12, 19, ...] · 완전잉여계(Complete Residue System) - 집합 0, 1, ... , m - 1 을 mod m 상에서의 완전잉여계라고 한다. 즉. % m 연산 결과의 집합, m으로 나눈 나머지 집합이다. 'm'을 다 모아둔 숫자를 완전잉여계라고 한다. ex) 11의 완전잉여계 원소 = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 'm'의 원소는 모두 몇 개인가? = m개 · 기약잉여계(Reduced Residue System) - 완전잉여계에서 m과 서로소인 원소의 집합을 기약잉여계라고 한다. * 서로소 : 두 수의 공..
더보기
