핵심 수론 | PromleeBlog

🚀

RSA: 키 생성 (RSA: Key Generation) 🔗

두 개의 큰 소수 p, q를 선택한다.
$N = p * q$ 를 계산한다.
$\phi(N) = (p - 1)(q - 1)$ 를 계산한다.
$e$ 를 선택한다. (단, $1 < e < \phi(N)$ 이고, $gcd(e, \phi(N)) = 1$ 이어야 한다.)
$d * e= 1 \pmod{\phi(N)}$ 를 만족하는 비밀 키 $d$ 를 계산한다.
공개 키 $pk$ 는 $(N, e)$ 이고, 비밀 키 $sk$ 는 $(N, d)$ 이다.

🚀

RSA: 암호화 & 복호화 (RSA: Encryption & Decryption) 🔗

암호화
- 공개 키 $pk = (N, e)$ 와 평문 $M$ 을 입력으로 받는다.
- $C := RSA.Enc(pk, M) = M^e \pmod{N}$ 을 계산한다.
- $C$ 를 반환한다.
복호화
- 비밀 키 $sk = (N, d)$ 와 암호문 $C$ 를 입력으로 받는다.
- $M' := RSA.Dec(sk, C) = C^d \pmod{N}$ 을 계산한다.
- $M'$ 을 반환한다.

🚀

모듈러 지수승 (Modular Exponentiation) 🔗

g^a \pmod{p}

를 계산하는 방법

Naive 한 방법 : (a-1)번의 곱셈이 필요하다.

✅

왼쪽에서 오른쪽 모듈러 지수승(L2RME) 🔗

입력:

g, a = (a_{l-1}, a_{l-2}, ... , a_1, a_0)_2, p

출력:

g^a \pmod{p}

왼쪽에서 오른쪽 모듈러 지수승

R = 1
for i from l - 1 down to 0 do
		R = R^2 (mod p)
		if a_i = 1 then
				R = R * g (mod p)
		end if
end for
return R

➡️

예시 (L2RME) 🔗

4^{25} \pmod{31}

을 계산하시오.

$25 = (11001)_2$ -> a를 2진수로 변환, $l = 5$
$a_4 = 1, a_3 = 1, a_2 = 0, a_1 = 0, a_0 = 1$
$a_4 = 1$ 이므로 $R = 1^2 * 4 \pmod{31} = 4$
$a_3 = 1$ 이므로 $R = 4^2*4 \pmod{31} = 2$
$a_2 = 0$ 이므로 $R = 2^2 \pmod{31} = 4$
$a_1 = 0$ 이므로 $R = 4^2 \pmod{31} = 16$
$a_0 = 1$ 이므로 $R = 16^2*4 \pmod{31} = 29$
따라서, $4^{25} \pmod{31} = 29$

log_2a + HW(a) - 1

번의 곱셈이 필요하다.

HW(a)

는 a의 비트 중 1의 개수이다.

✅

오른쪽에서 왼쪽 모듈러 지수승(R2LME) 🔗

입력:

g, a = (a_{l-1}, a_{l-2}, ... , a_1, a_0)_2, p

출력:

g^a \pmod{p}

오른쪽에서 왼쪽 모듈러 지수승

R = 1, T = g
for i from 0 to l - 2 do
		if a_i = 1 then
				R = R * T (mod p)
		end if
		T = T^2 (mod p)
end for
R = R * T (mod p)
return R

➡️

예시 (R2LME) 🔗

4^{25} \pmod{31}

을 계산하시오.

$25 = (11001)_2$ -> a를 2진수로 변환, $l = 5$
$a_0 = 1$ 이므로 $R = 1 * 4 \pmod{31} = 4, T = 4$
$a_1 = 0$ 이므로 $R = 4, T = 4^2 \pmod{31} = 16$
$a_2 = 0$ 이므로 $R = 4, T = 16^2 \pmod{31} = 25$
$a_3 = 1$ 이므로 $R = 4 * 25 \pmod{31} = 29, T = 25^2 \pmod{31} = 4$
$a_4 = 1$ 이므로 $R = 29 * 4 \pmod{31} = 29$
따라서, $4^{25} \pmod{31} = 29$

log_2a + HW(a) - 1

번의 곱셈이 필요하다.

HW(a)

는 a의 비트 중 1의 개수이다.

🚀

정수 위의 유클리드 알고리즘 (Euclidean Algorithm on Integers) 🔗

a와 b가 양의 정수이고 a > b일 때, $\gcd(a, b) = \gcd(b, a \pmod{b})$ 이다.

입력: 두 양의 정수 a, b (a >= b)

출력: a와 b의 최대공약수

정수 위의 유클리드 알고리즘

r = a, r' = b
while r' != 0 do
		r'' = r mod r'
		r = r'
		r' = r''
end while
d = r
return d

✅

예시 (정수 위의 유클리드 알고리즘) 🔗

\gcd(48, 18)

을 계산하시오.

$48 = 18 * 2 + 12$
$18 = 12 * 1 + 6$
$12 = 6 * 2 + 0$
따라서, $\gcd(48, 18) = 6$

🚀

확장된 유클리드 알고리즘 (Extended Euclidean Algorithm) 🔗

$a, b, r$ 이 양의 정수이고 $d = \gcd(a, b)$ 일 때, $ax + by = d$ 이 성립하며
$x, y \in \mathbb{Z}$ 는 $d|r$ 일 때 존재한다.( $d|r$ 은 $d$ 가 $r$ 을 나눈다는 의미이다.)

입력: 두 양의 정수

a, b (a >= b)

출력:

a

와

b

의 최대공약수 d와

d = ax + by

를 만족하는

x, y

확장된 유클리드 알고리즘

r = a, r' = b, x = 1, y = 0, x' = 0, y' = 1
while r' != 0 do
		q = r // r'
		r'' = r mod r'
		(r, x, y, r', x', y') = (r', x', y', r'', x - q * x', y - q * y')
end while
d = r
return d, x, y

✅

예시 (확장된 유클리드 알고리즘) 🔗

\gcd(48, 18)

을 계산하시오.

$r = 48, r' = 18, x = 1, y = 0, x' = 0, y' = 1$
$q = 48 // 18 = 2, r'' = 48 \pmod {18} = 12$ , $(r, x, y, r', x', y')\\ = (18, 0, 1, 12, 1 - 2 * 0, 0 - 2 * 1) = (18, 0, 1, 12, 1, -2)$
$q = 18 // 12 = 1, r'' = 18 \pmod {12} = 6$ , $(r, x, y, r', x', y')\\ = (12, 1, -2, 6, 0 - 1 * 1, 1 - 1 * -2) = (12, 1, -2, 6, -1, 3)$
$q = 12 // 6 = 2, r'' = 12 \pmod {6} = 0$ , $(r, x, y, r', x', y')\\ = (6, -1, 3, 0, 1 - 2 * -1, -2 - 2 * 3) = (6, -1, 3, 0, 3, -8)$
따라서, $\gcd(48, 18) = 6$ 이고, $6 = -1 * 48 + 3 * 18$ 이다.

🚀

오일러 파이 함수 (Euler's Phi Function) 🔗

오일러 파이 함수 $\phi(n)$ 은 $\mathbb{Z}_m$ 에서 m과 서로소인 수의 개수를 의미한다.

m = p_1^{e_1} * p_2^{e_2} * ... * p_n^{e_n}

일 때(이때,

p_i

는 서로 다른 소수,

e_i

는 양의 정수),

\phi(n)

은 다음과 같이 계산할 수 있다.

👨‍💻

\phi(n) = \prod _{i=1}^{n}(p_i^{e_i} - p_i^{e_i-1})

\phi(p) = p - 1

(p는 소수)

✅

예시 (오일러 파이 함수) 🔗

$\phi(6) = 2$ (6과 서로소인 수는 1, 5), $\phi(8) = 4$ (8과 서로소인 수는 1, 3, 5, 7)
$m = 240$ 이라 하면, $240 = 2^4 * 3^1 * 5^1$ 이므로

\phi(240) = (2^4 - 2^3) * (3^1 - 3^0) * (5^1 - 5^0) = 64

🚀

오일러 정리 (Euler's Theorem) 🔗

👨‍💻

서로 서로수인 정수

a

, 정수

m

에 대하여,

a^{\phi(m)} \equiv 1 \pmod{m}

이다.

✅

예시 (오일러 정리) 🔗

a = 5, m = 12

일 때,

\phi(12) = \phi(2^2 * 3^1) = (2^2 - 2^1) * (3^1 - 3^0) = 4

이다.

\because (1, 5, 7, 11)

따라서,

5^4 \equiv 1 \pmod{12}

이다.

🚀

페르마의 소정리 (Fermat's Little Theorem) 🔗

👨‍💻

정수

a

, 소수

p

에 대하여,

a^{p} \equiv a \pmod{p}

이다.

✅

예시 (페르마의 소정리) 🔗

$p = 7, a = 2$ 일 때, $2^7 \equiv 2 \pmod{7}$ 이다.
$p = 11, a = 3$ 일 때, $3^{11} \equiv 3 \pmod{11}$ 이다.

✅

따름정리 (페르마의 소정리) 🔗

👨‍💻

정수

a

, 소수

p

에 대하여,

a^{p-1} \equiv 1 \pmod{p}

이다.
또한,

a^{-1} = a^{p-2} \pmod{p}

이다.

✅

증명 (페르마의 소정리) 🔗

a\times a \times a \times ... \times a \equiv a \pmod{p}

이므로,

a^{p-1} \equiv 1 \pmod{p}

이다.

a \times a^{-1} \equiv 1 \pmod{p}

이므로,

a^{-1} = a^{p-2} \pmod{p}

이다.

🚀

중국인의 나머지 정리 (Chinese Remainder Theorem) 🔗

👨‍💻

p

와

q

가 서로소일 때, 두 방정식

x ≡ a \pmod{p}

x ≡ b \pmod{q}

은

pq

에 대한

x

의 유일한 해를 가진다.

✅

증명 (중국인의 나머지 정리) 🔗

존재성
$x = a \times q \times M_q + b \times p \times M_p \pmod{pq}$ $x = a \times q \times M_{q} + b \times p \times M_{p} (mod pq)$
여기서 $M_q$ $M_{q}$ 는 $q^{-1} \pmod{p}$ $q^{- 1} (mod p)$ 이고, $M_p$ $M_{p}$ 는 $p^{-1} \pmod{q}$ $p^{- 1} (mod q)$ 이다.
- 예시
  $x ≡ 3 \pmod{7}$ 이고 $x ≡ 5 \pmod{15}$ 일 때
  $M_q = 15^{-1} \pmod{7} = 1$ , $M_p = 7^{-1} \pmod{15} = 13$
  $x = 3 * 15 * 1 + 5 * 7 * 13 = 500$ 이고, 이를 105로 나눈 나머지는 80이다.
유일성
만약 $x ≡ y \pmod{p}$ $x \equiv y (mod p)$ 이고 $x ≡ y \pmod{q}$ $x \equiv y (mod q)$ 라면, $x - y$ $x - y$ 는 $p$ $p$ 와 $q$ $q$ 의 배수이다.
따라서, $x - y$ $x - y$ 는 $pq$ $pq$ 의 배수이며 $x ≡ y \pmod{pq}$ $x \equiv y (mod pq)$ 이다.
- 예시
  $x ≡ 3 \pmod{7}$ 이고 $x ≡ 5 \pmod{15}$ 일 때
  $x-y$ 는 7과 15의 배수이므로, $x ≡ y \pmod{105}$ 이다.

✅

예시 (중국인의 나머지 정리) 🔗

\mathbb{Z}_{105}

에서

x ≡ 3 \pmod{7}

이고

x ≡ 5 \pmod{15}

인

x

를 찾으시오.

$105 = 15 * 7$ , $\gcd (15, 7) = 1$
$p = 7, q = 15$ 로 둔다.
$M_q$ 는 $q^{-1} \pmod{p}$ 이고, 여기서는 $15^{-1} \pmod{7} = 1$ 이다. (왜냐하면 15를 7로 나눈 나머지는 1이고 1의 역원은 1임.)
$M_p$ 는 $p^{-1} \pmod{q}$ 이고, 여기서는 $7^{-1} \pmod{15} = 13$ 이다. (왜냐하면 $7 * 13 = 91$ 은 15로 나눈 나머지가 1이기 때문.)
$x$ 는 $a * q * M_q + b * p * M_p$ 로 계산할 수 있으며, $x = 3 * 15 * 1 + 5 * 7 * 13 = 500$ 이고, 이를 105로 나눈 나머지는 80이다.

따라서

x ≡ 80 \pmod{105}

이다.

🚀

확률적 소수 판정법 I: 페르마 검사 (Probabilistic Primality Test I: Fermat Test) 🔗

a를 정수, p를 소수라고 할 때,

a^p ≡ a (mod p) (\Longleftrightarrow a^{ p-1} ≡ 1 (mod p))

✅

알고리즘 5. 페르마 소수 판정법 🔗

입력: 후보

\bar{p}

와 보안 매개변수 λ

출력: "

\bar{p}

은 소수이다" 혹은 "

\bar{p}

은 합성수이다"

페르마 소수 판정법, p -> p{bar}

for i from 1 to λ do
		randomly select a from {2, 3, ..., p - 2}
		if a^{p-1} ≡ 1 (mod p)이 아니라면
				return "p은 합성수이다"
		end if
end for
return "p은 소수이다"

1부터 λ까지 아래
2~3
과정을 반복한다.
2부터 p - 2 사이의 무작위 수 a를 선택한다.
$a^{p-1} ≡ 1 (mod p)$ 이 아니라면, p는 합성수이다.
모든 테스트를 통과하면 p는 소수일 가능성이 높다.

➡️

정리 (페르마 검사) 🔗

주어진 수가 소수인지 합성수인지 판별하는 확률적 알고리즘

페르마의 소정리

를 기반으로 함

보안 매개변수 λ만큼 많은 수의 무작위 테스트를 수행

각 테스트에서, 2와 p - 2 사이의 무작위 수 a를 선택하고

a^{p-1}

을 계산한 후 이 결과가 p에 대한

(mod\;1)

과 같은지 확인

만약

a^{p-1} ≡ 1 (mod p)

이 성립하지 않는 경우가 하나라도 발견되면 p는 합성수

🚀

반례: 카마이클 수 (Counterexample: Carmichael Number) 🔗

카마이클 수 C는 합성수이며 모든 a에 대해 $gcd(a, C) = 1$ 일 때 다음을 만족하는 수이다.
$a^{C-1} ≡ 1 \pmod{C}$

✅

예시 (카마이클 수) 🔗

•

N = 561 = 3 * 11 * 17

• 모든 a에 대해

gcd(a, 561) = 1

일 때,

a^{560} ≡ 1 (mod 561)

• 페르마 검사는 카마이클 수를 소수로 판별한다.

• 대략 10^6 개의 카마이클 수가 10^15 이하에 존재한다.

➡️

정리 (카마이클 수) 🔗

카마이클 수는 페르마의 소정리 조건을 만족하지만 합성수인 특별한 종류의 수이다.

즉,

a^{C-1} ≡ 1 (mod C)

를 만족하지만 C는 소수가 아닌 수를 말한다.

카마이클 수는 페르마 검사에서 소수로 잘못 판별될 수 있는 '가짜 소수'의 한 예시

🚀

확률적 소수 판정법 II: 밀러-라빈 검사 (Probabilistic Primality Test II: Miller-Rabin Test) 🔗

\bar{p} - 1 = 2^r * s

형태이고 s가 홀수일 때, 만약

a^s \neq 1 \pmod{\bar{p}}

를 만족하는 어떤 정수 a에 대해 모든

j \in \{0, 1, ..., r - 1\}

가

a^{s*2^j} \neq \bar{p} - 1 \pmod{\bar{p}}

를 만족하면,

\bar{p}

은 합성수이다.

그렇지 않다면,

\bar{p}

은 아마도 소수일 것이다.

✅

예시 (밀러-라빈 검사) 🔗

$\bar{p} = 561 = 3 * 11 * 17$
$\bar{p} - 1 = 560 = 2^4 * 35$

5^{35} ≡ 23 \pmod {561}

5^{35*2} ≡ 529 \pmod {561}

5^{35*2^2} ≡ 529^2 ≡ 463 \pmod {561}

5^{35*2^3} ≡ 463^2 ≡ 67 \pmod {561}

\Longrightarrow

561은 합성수이다!

➡️

정리 (밀러-라빈 검사) 🔗

밀러-라빈 검사는 페르마 검사보다 더 정확한 확률적 소수 판정법

\bar{p} - 1 = 2^r * s

형태로 표현되는 홀수 s에 대해 작동

임의의 a에 대해

a^s

를 계산하고 이 결과가 1 또는

\bar{p} - 1

과 다를 경우

a^{s*2}, a^{s*2^2}, ..., a^{s*2^{r-1}}

의 계산을 이어간다.

이 수들 중 하나라도

\bar{p} - 1

과 동일하다면,

\bar{p}

은 소수일 가능성이 높다.

그러나 이 모든 수가

\bar{p} - 1

과 다르다면

\bar{p}

은 합성수이다.

🚀

밀러-라빈 소수 판정법 설명 (Miller-Rabin Primality Test Explanation) 🔗

✅

알고리즘 6. 밀러-라빈 소수 판정법 🔗

입력: 후보

\bar{p}

와

\bar{p} - 1 = 2^r * s

형태의 s는 홀수, 보안 매개변수 λ

출력: "

\bar{p}

은 소수이다" 혹은 "

\bar{p}

은 합성수이다"

밀러-라빈 소수 판정법, p -> p{bar}

for i from 1 to λ do
		randomly select a from {2, 3, ..., p - 2}
		z = a^s (mod p)
		if z ≠ 1 and z ≠ p - 1이라면
				for j from 1 to r - 1 do
						z = z^2 (mod p)
						if z = 1이라면
								return "p은 합성수이다"
						end if
						if z = p - 1이라면
								break
						end if
				end for
				if z ≠ p - 1이라면
						return "p은 합성수이다"
				end if
		end if
end for
return "p은 소수이다"

최악의 경우 실패 확률은

4^{-λ}

이다.

추천 포스트

핵심 수론Essential Number Theory

RSA: 키 생성 (RSA: Key Generation) 🔗

RSA: 암호화 & 복호화 (RSA: Encryption & Decryption) 🔗

모듈러 지수승 (Modular Exponentiation) 🔗

왼쪽에서 오른쪽 모듈러 지수승(L2RME) 🔗

예시 (L2RME) 🔗

오른쪽에서 왼쪽 모듈러 지수승(R2LME) 🔗

예시 (R2LME) 🔗

정수 위의 유클리드 알고리즘 (Euclidean Algorithm on Integers) 🔗

예시 (정수 위의 유클리드 알고리즘) 🔗

확장된 유클리드 알고리즘 (Extended Euclidean Algorithm) 🔗

예시 (확장된 유클리드 알고리즘) 🔗

오일러 파이 함수 (Euler's Phi Function) 🔗

예시 (오일러 파이 함수) 🔗

오일러 정리 (Euler's Theorem) 🔗

예시 (오일러 정리) 🔗

페르마의 소정리 (Fermat's Little Theorem) 🔗

예시 (페르마의 소정리) 🔗

따름정리 (페르마의 소정리) 🔗

증명 (페르마의 소정리) 🔗

중국인의 나머지 정리 (Chinese Remainder Theorem) 🔗

증명 (중국인의 나머지 정리) 🔗

예시 (중국인의 나머지 정리) 🔗

확률적 소수 판정법 I: 페르마 검사 (Probabilistic Primality Test I: Fermat Test) 🔗

알고리즘 5. 페르마 소수 판정법 🔗

정리 (페르마 검사) 🔗

반례: 카마이클 수 (Counterexample: Carmichael Number) 🔗

예시 (카마이클 수) 🔗

정리 (카마이클 수) 🔗

확률적 소수 판정법 II: 밀러-라빈 검사 (Probabilistic Primality Test II: Miller-Rabin Test) 🔗

예시 (밀러-라빈 검사) 🔗

정리 (밀러-라빈 검사) 🔗

밀러-라빈 소수 판정법 설명 (Miller-Rabin Primality Test Explanation) 🔗

알고리즘 6. 밀러-라빈 소수 판정법 🔗

핵심 수론
Essential Number Theory