정수론과 모듈러 연산: 단계별 풀이가 있는 연습 문제

그림, 힌트, 자세한 풀이가 있는 무료 정수론과 모듈러 연산 연습 문제. 매번 새로운 값으로, 세 가지 난이도: 최대공약수와 나머지, 역원과 합동식, 모듈러 거듭제곱과 RSA.

무료 연습 문제쉬움
012345678910mod 11

0 ≤ r < 11인 나머지 r, 곧 942 mod 11을(를) 구하시오.

a = 942n = 11

정확한 답: 정수, 반올림하지 않음.

다음 문제 →
정수론과 모듈러 연산 무료로 연습하기지금 정수론과 모듈러 연산 연습하기매일 무료 문제 5개. 카드 등록이 필요 없습니다.

연습 내용

  1. 쉬움최대공약수와 나머지
  2. 보통역원과 합동식
  3. 어려움모듈러 거듭제곱과 RSA

정수론과 모듈러 연산 문제 푸는 방법

  1. 먼저 모든 수를 n으로 나눈 나머지로 줄이세요. 나머지는 0부터 n − 1 사이에 있습니다.
  2. 최대공약수는 유클리드 호제법으로 계속 나누세요. 0이 아닌 마지막 나머지가 최대공약수입니다.
  3. 역원은 확장 알고리즘을 실행해 a의 계수를 취하고, 음수이면 n을 더하세요.
  4. a·x ≡ b는 a⁻¹을 곱해서 풀고, 두 합동식은 x = r₁ + m₁k로 써서 합치세요.
  5. 거듭제곱은 지수를 이진수로 쓰고 거듭 제곱하세요. RSA에서는 d = e⁻¹ mod φ(n)이고 φ(n) = (p − 1)(q − 1)입니다.

흔한 실수

  • 음수에 대해 음의 나머지를 답하는 것.
  • 유클리드 호제법을 첫 번째 나머지에서 멈추는 것.
  • 역원을 음수로 둔 채 n을 더하지 않는 것.
  • RSA 지수 d를 φ(n)이 아니라 n으로 나눈 나머지로 구하는 것.
  • 페르마 정리에서 지수를 p − 1이 아니라 p로 나눈 나머지로 줄이는 것.

핵심 공식

나머지가 있는 나눗셈
a = q·n + r, 0 ≤ r < n
유클리드
gcd(a, b) = gcd(b, a mod b)
최소공배수
lcm(a, b) = a·b/gcd(a, b)
역행렬
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
일차 합동식
a·x ≡ b → x ≡ a⁻¹·b (mod n)
오일러 피 함수
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
페르마
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

정수론과 모듈러 연산 처음부터 배우기

1나머지와 합동

a를 n으로 나누면 몫 q와 나머지 r이 나옵니다: a = q·n + r, 0 ≤ r < n. 나머지는 a mod n으로 씁니다. 음수에서는 q도 음수입니다: −3 = −1·7 + 4이므로 −3 mod 7 = 4입니다.

두 수가 같은 나머지를 가질 때, 곧 n이 a − b를 나눌 때 두 수는 n을 법으로 합동이라 하고 a ≡ b (mod n)으로 씁니다.

0123456mod 7−3 ≡ 411 ≡ 4

나머지는 단계마다 줄일 수 있으며 수를 작게 유지해 줍니다.

(a + b) mod n = ((a mod n) + (b mod n)) mod n, a·b도 마찬가지

예를 들어 47·58 mod 9: 47 ≡ 2이고 58 ≡ 4이므로 47·58 ≡ 8 (mod 9)입니다.

자가 점검 −17 mod 5는 얼마인가?
  1. 2
  2. 3
  3. −2
  4. −3

답: 3. −17 = −4·5 + 3이므로 나머지는 3입니다. 2는 17 mod 5의 답이고, 나머지는 결코 음수가 아닙니다.

2유클리드 호제법

최대공약수 gcd(a, b)는 두 수를 모두 나누는 가장 큰 수입니다. 유클리드 호제법은 gcd(a, b) = gcd(b, a mod b)를 이용합니다.

  1. 나눕니다: a = q·b + r.
  2. (a, b)를 (b, r)로 바꿉니다.
  3. 나머지가 0이 될 때까지 반복합니다. 0이 아닌 마지막 나머지가 gcd입니다.
252 = 2·105 + 42, 105 = 2·42 + 21, 42 = 2·21 + 0 → gcd = 21

최소공배수는 이로부터 나옵니다: lcm(a, b) = a·b / gcd(a, b).

자가 점검 gcd(84, 36)은 얼마인가?
  1. 12
  2. 252
  3. 4
  4. 6

답: 12. 84 = 2·36 + 12이고 36 = 3·12 + 0이므로 gcd는 12입니다. 252는 최소공배수 84·36/12입니다.

3역원과 확장 알고리즘

n을 법으로 하는 a의 역원은 a·x ≡ 1 (mod n)인 수 x입니다. 이는 gcd(a, n) = 1일 때, 그리고 그때에만 존재합니다.

확장 유클리드 알고리즘은 (n, a)에 유클리드 호제법을 실행하면서 각 나머지마다 계수 t를 기록하여 모든 나머지 r ≡ t·a (mod n)이 되게 합니다. n에는 t = 0, a에는 t = 1에서 시작하고, 새 t는 두 줄 위의 t에서 q 곱하기 한 줄 위의 t를 뺀 값입니다. 나머지 1이 나타나면 그 t가 역원입니다.

역원이 있으면 합동식 a·x ≡ b (mod n)은 x ≡ a⁻¹·b로 풉니다. d = gcd(a, n)이 1보다 크면 d가 b를 나눌 때 해가 d개이고, 나누지 않으면 해가 없습니다.

법이 서로소인 두 합동식 x ≡ r₁ (mod m₁)과 x ≡ r₂ (mod m₂)는 m₁·m₂를 법으로 해가 정확히 하나 있습니다(중국인의 나머지 정리). x = r₁ + m₁k로 쓰고 k를 구하세요.

풀이 예제

40을 법으로 하는 7의 역원을 구하시오.

1

(40, 7)에 유클리드 호제법

40 = 5·7 + 5, 7 = 1·5 + 2, 5 = 2·2 + 1
2

계수 t 추적

t(40) = 0, t(7) = 1.

t(5) = 0 − 5·1 = −5, t(2) = 1 − 1·(−5) = 6, t(1) = −5 − 2·6 = −17
3

양수로 만들기

1 ≡ −17·7 (mod 40)이고 −17 + 40 = 23입니다.

4

검산

7·23 = 161 = 4·40 + 1
답

역원은 7⁻¹ ≡ 23 (mod 40)입니다.

4모듈러 거듭제곱과 RSA

반복 제곱법은 aᵏ mod n을 빠르게 계산합니다. k를 이진수로 쓰고, 제곱하고 나머지를 취해 a, a², a⁴, a⁸, … mod n을 구한 뒤, 비트가 1인 거듭제곱들을 곱합니다.

페르마의 소정리: 소수 p가 a를 나누지 않으면 aᵖ⁻¹ ≡ 1 (mod p)입니다. 따라서 지수를 p − 1을 법으로 줄일 수 있습니다.

RSA는 두 소수 p와 q로 키를 만듭니다.

  1. n = p·q, φ(n) = (p − 1)(q − 1).
  2. gcd(e, φ(n)) = 1인 e를 고릅니다. (n, e)가 공개 키입니다.
  3. d = e⁻¹ mod φ(n)을 계산합니다. 이것이 개인 키입니다.
  4. 암호화 c = mᵉ mod n, 복호화 m = cᵈ mod n.

오일러 φ(n)은 1부터 n까지의 수 중 n과 서로소인 수의 개수입니다: 소수 p에서 φ(p) = p − 1, φ(pᵏ) = pᵏ − pᵏ⁻¹이며, 서로소인 인수들에 대해 φ는 곱셈적입니다.

자가 점검 RSA 키가 p = 5, q = 11, e = 3을 쓴다. d는 얼마인가?
  1. 13
  2. 27
  3. 37
  4. 3

답: 27. φ(n) = 4·10 = 40이고 3·27 = 81 = 2·40 + 1이므로 d = 27입니다. n = 55를 법으로 한 3의 역원은 37이겠지만, d는 φ(n)을 법으로 구합니다.

5흔한 실수

  • 음수에 대해 음의 나머지를 답하는 것: −17 mod 5는 −2가 아니라 3입니다.
  • 유클리드 호제법을 0이 아닌 마지막 나머지가 아니라 첫 번째 나머지에서 멈추는 것.
  • 확장 알고리즘에서 나온 음수 계수에 n을 더하는 것을 잊는 것.
  • RSA 지수 d를 φ(n)이 아니라 n을 법으로 계산하는 것.
  • 페르마 정리에서 지수를 p − 1이 아니라 p를 법으로 줄이는 것.

6시험 문제의 유형

  • 쉬움: 최대공약수와 나머지. 유클리드 호제법으로 gcd나 lcm을 구하고, 음수의 나머지를 구하고, 합과 곱을 n을 법으로 줄입니다.
  • 보통: 역원과 합동식. 확장 알고리즘으로 모듈러 역원을 구하고, 일차 합동식을 풀고, 중국인의 나머지 정리로 두 합동식을 합치고, 오일러 φ(n)을 계산합니다.
  • 어려움: 모듈러 거듭제곱과 RSA. 반복 제곱법과 페르마 정리를 쓰고, 해가 여러 개인 합동식을 풀고, RSA 개인 지수, 암호문, 복호화한 메시지를 구합니다.

앱에서 단계별로 배우기앱에서 단계별로 배우기

예제 풀이

예제 1쉬움

큰 수를 직접 곱하지 말고 (914·953) mod 11을(를) 구하세요. 먼저 나머지로 줄이세요.

n = 11

구하는 값: (914·953) mod 11

힌트 보기
  1. (x·y) mod n = ((x mod n)·(y mod n)) mod n이며 합에서도 마찬가지입니다.
  2. 914 mod 11 = 1, 953 mod 11 = 7.
  3. 나머지들의 곱을 11을(를) 법으로 줄이세요.
정답과 단계별 풀이 보기

나누어떨어짐과 나머지: a mod n은 0 ≤ r < n이고 a = q·n + r인 나머지 r이며, a가 음수일 때도 마찬가지입니다. 유클리드 호제법은 a = q·b + r을 반복하고 (a, b)를 (b, r)로 바꾸어 gcd(a, b)를 구합니다. 0이 아닌 마지막 나머지가 gcd입니다. 그러면 lcm(a, b) = a·b/gcd(a, b)입니다. 나머지는 단계마다 줄일 수 있습니다. (a + b) mod n과 (a·b) mod n은 a mod n과 b mod n에만 의존합니다.

각 수를 줄이기

914 ≡ 1, 953 ≡ 7 (mod 11)

합치기

1·7 = 7 ≡ 7 (mod 11)

답

(914·953) mod 11 = 7
예제 2보통

오일러 피 함수 φ(637), 곧 1부터 637까지의 정수 중 637와(과) 서로소인 수의 개수를 구하시오.

n = 637 = 72·13

구하는 값: φ(637)

힌트 보기
  1. n을 소인수분해하세요: 637 = 72·13.
  2. φ는 서로소인 인수에 대해 곱셈적이며, φ(pᵏ) = pᵏ − pᵏ⁻¹입니다.
  3. φ(n) = n·∏(1 − 1/p).
정답과 단계별 풀이 보기

역원과 합동식: a는 gcd(a, n) = 1일 때, 그리고 그때에만 n을 법으로 하는 역원을 가집니다. 확장 유클리드 알고리즘은 1 = s·n + t·a로 쓰고, 그러면 a⁻¹ ≡ t (mod n)입니다. gcd(a, n) = 1인 합동식 a·x ≡ b (mod n)의 해는 x ≡ a⁻¹·b입니다. 법이 서로소인 두 합동식 x ≡ r₁ (mod m₁)과 x ≡ r₂ (mod m₂)는 m₁·m₂를 법으로 해가 하나 있습니다(중국인의 나머지 정리). 오일러 φ(n)은 1부터 n까지의 수 중 n과 서로소인 수의 개수입니다: φ(n) = n·∏(1 − 1/p).

소인수

637 = 72·13

오일러 피 함수 값

φ(637) = φ(49)·φ(13) = 42·12 = 504

답

φ(637) = 504
예제 3어려움
mc = me​ mod n225m = cd​ mod n?(n, e) = (481, 23)d

RSA 키가 p = 13, q = 37, e = 23를 쓴다. 암호문 c = 225을(를) 복호화하시오. 메시지 m을(를) 구하시오.

p = 13q = 37e = 23c = 225

구하는 값: m

힌트 보기
  1. n = 481, φ(n) = 432.
  2. d = e⁻¹ mod φ(n) = 263.
  3. m = cd mod n = 225263 mod 481: 반복 제곱법을 사용하세요.
정답과 단계별 풀이 보기

모듈러 거듭제곱과 RSA: aᵏ mod n은 반복 제곱법으로 계산합니다. k를 이진수로 쓰고, 제곱하고, 단계마다 나머지를 취하고, 비트가 1인 거듭제곱들을 곱하세요. 페르마: a를 나누지 않는 소수 p에 대해 aᵖ⁻¹ ≡ 1 (mod p)이므로 지수를 p − 1을 법으로 줄일 수 있습니다. RSA: 소수 p와 q를 고르고, n = p·q, φ(n) = (p − 1)(q − 1)입니다. 공개 지수 e는 φ(n)과 서로소이고 개인 지수는 d = e⁻¹ mod φ(n)입니다. c = mᵉ mod n으로 암호화하고 m = cᵈ mod n으로 복호화합니다.

개인 지수

n = 481, φ(n) = 432
d = 23−1 mod 432 = 263

반복 제곱법으로 복호화하기

263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)

메시지

m = 361
검산: 36123 mod 481 = 225

답

m = 361

질문과 답변

정수론과 모듈러 연산: 무엇인가요?

a를 n으로 나누면 몫 q와 나머지 r이 나옵니다: a = q·n + r, 0 ≤ r < n. 나머지는 a mod n으로 씁니다. 음수에서는 q도 음수입니다: −3 = −1·7 + 4이므로 −3 mod 7 = 4입니다.

두 수가 같은 나머지를 가질 때, 곧 n이 a − b를 나눌 때 두 수는 n을 법으로 합동이라 하고 a ≡ b (mod n)으로 씁니다.

정수론과 모듈러 연산 문제는 어떻게 단계별로 푸나요?
  1. 먼저 모든 수를 n으로 나눈 나머지로 줄이세요. 나머지는 0부터 n − 1 사이에 있습니다.
  2. 최대공약수는 유클리드 호제법으로 계속 나누세요. 0이 아닌 마지막 나머지가 최대공약수입니다.
  3. 역원은 확장 알고리즘을 실행해 a의 계수를 취하고, 음수이면 n을 더하세요.
  4. a·x ≡ b는 a⁻¹을 곱해서 풀고, 두 합동식은 x = r₁ + m₁k로 써서 합치세요.
  5. 거듭제곱은 지수를 이진수로 쓰고 거듭 제곱하세요. RSA에서는 d = e⁻¹ mod φ(n)이고 φ(n) = (p − 1)(q − 1)입니다.
정수론과 모듈러 연산에서 자주 하는 실수는?
  • 음수에 대해 음의 나머지를 답하는 것.
  • 유클리드 호제법을 첫 번째 나머지에서 멈추는 것.
  • 역원을 음수로 둔 채 n을 더하지 않는 것.
  • RSA 지수 d를 φ(n)이 아니라 n으로 나눈 나머지로 구하는 것.
  • 페르마 정리에서 지수를 p − 1이 아니라 p로 나눈 나머지로 줄이는 것.
정수론과 모듈러 연산 연습에서는 무엇을 다루나요?
  • 쉬움: 최대공약수와 나머지
  • 보통: 역원과 합동식
  • 어려움: 모듈러 거듭제곱과 RSA

문제마다 값이 새로 바뀌므로 답이 아니라 푸는 방법을 익히게 됩니다. 막혔나요? 먼저 작은 힌트를 열고, 필요할 때만 전체 해설을 보세요.

연습 방법

  • 문제마다 값이 새로 바뀌므로 답이 아니라 푸는 방법을 익히게 됩니다.
  • 막혔나요? 먼저 작은 힌트를 열고, 필요할 때만 전체 해설을 보세요.
  • 진행 상황, 틀린 문제, 저장한 문제가 보관되므로 시험 전에 복습할 수 있습니다.

이 주제가 포함된 강의

컴퓨터과학 기초이산수학

수학과 통계의 다른 주제

극한도함수최적화적분수열과 급수다변수 미적분미분방정식복소수수치해석행렬과 행렬식벡터: 내적과 외적명제논리와 증명집합, 관계, 함수그래프 이론확률기술통계정규분포신뢰구간가설 검정과 신뢰구간선형 회귀와 상관카이제곱 검정

인쇄용 학습지

정답이 있는 정수론과 모듈러 연산 학습지
정수론과 모듈러 연산 무료로 연습하기지금 정수론과 모듈러 연산 연습하기매일 무료 문제 5개. 카드 등록이 필요 없습니다.