31. Number-Theoretic Algorithms

정수론 알고리즘에 대해 알아보자.

Size of inputs and cost of arithmetic computations

정수에 대한 알고리즘은 그 정수를 나타내는 데 드는 비트수로 나타낸다. 그 비트수에 대해 다항식 시간이 들면 다항 시간 알고리즘으로 정의한다. 정수론 알고리즘에서는 얼마나 많은 비트 연산이 들어가는지를 기준으로 삼는다.

31.1. Elementary number-theoretic notions

기본적 정수론 개념들을 알아보자.

Divisibility and divisors

d가 a를 나누면 d | a로 표기하고 a가 d의 배수라 하고 d를 a의 약수라 한다. 모든 양의 정수는 자명한 약수 1, a를 갖는다. 비자명 약수는 a의 인수이다.

Prime and composite numbers

자명한 약수만 갖는 자연수를 소수라 한다. 소수가 아니면 합성수라 한다. 1은 단위수로 소수도 합성수도 아니다.

The division theorem, remainders, and modular equivalence

나머지 정리를 알아보자.

Theorem. (Division theorem) 양의 정수 n과 정수 a에 대해 a = qn + r, 0 \leq r < n이 되는 정수 q, r은 유일하다.

q = \lfloor \frac{a}{n} \rfloor, r = a \mod n나머지라 한다. 정수는 n에 대한 나머지를 통해 법 n에 대한 동치류로 분류할 수 있다.

Common divisors and greatest common divisors

d가 a의 약수이면서 b의 약수면 a, b의 공약수라 한다. a, b의 최대공약수는 가장 큰 공약수이다.

Theorem. a, b가 0이 아닌 정수라면 gcd(a, b)는 \{ax + by : x, y \in \mathbb{Z}\}의 최소 양수이다.

Corollary. a, b의 공약수는 최대공약수의 약수이다.

Corollary. n이 0이 아닌 정수라면 gcd(na, nb) = n gcd(a, b)이다.

Corollary. 양의 정수 n, a, b에 대해 n | ab고 gcd(a, n) = 1이면 n | b이다.

Relatively prime integers

최대공약수가 1인 두 정수를 서로소라 한다.

Theorem. a, p가 서로소고 b, p가 서로소면 ab, p도 서로소이다.

정수들이 그 정수들 내 모든 쌍이 서로소면 쌍별 서로소라 한다.

Unique factorization

다음은 소수로 나누기에 대한 중요한 특성이다.

Theorem. p가 소수고 a, b가 정수이고 p | ab이면 p | a 또는 p | b이다.

Theorem. (Unique factorization) 합성수 a를 소인수분해하는 방법은 유일하다.

31.2. Greatest common divisor

최대공약수를 계산하는 유클리드 알고리즘을 알아보자.

Theorem. (GCD recursion theorem) 음이 아닌 정수 a와 양의 정수 b에 대해 gcd(a, b) = gcd(b, a mod b)이다.

Euclid’s algorithm

위로부터 도출되는 유클리드 알고리즘은 다음과 같다.

EUCLID(a, b)
if b == 0
    return a
else
    return EUCLID(b, a mod b)

The running time of Euclid’s algorithm

유클리드 알고리즘의 수행 시간을 알아보자.

Lemma. a > b \geq 1이고 EUCLID(a, b)가 k \geq 1번의 재귀 호출을 한다면 a \geq F_{k+2}, b \geq F_{k+1}이다.

Theorem. (Lame’s theorem) k \geq 1에 대해 a > b \geq 1, b < F_{k+1}이면 EUCLID(a, b)는 k회 미만의 재귀 호출을 한다.

The extended form of Euclid’s algorithm

유클리드 알고리즘을 확장하면 다음과 같다.

EXTENDED-EUCLID(a, b)
if b == 0
    return (a, 1, 0)
else
    (d', x', y') = EXTENDED-EUCLID(b, a mod b)
    (d, x, y) = (d', y', x' - floor(a/b) y')
    return (d, x, y)

31.3. Modular arithmetic

모듈러 연산을 알아보자.

Finite group

(S, \oplus)는 결합법칙이 성립하고 항등원역원이 존재하는 이항 연산 \oplus에 대해 닫혀 있는 집합을 나타낸다. 교환법칙까지 성립하면 아벨군이라 한다. 원소가 유한하면 유한군이라 한다.

The groups defined by modular addition and multiplication

모듈러 덧셈 연산으로 정의된 군을 법 n 덧셈군 (\mathbb{Z}_{n}, +_{n})이라 한다.

Theorem. 법 n 덧셈군은 유한아벨군이다.

모듈러 곱셈 연산으로 정의된 군을 법 n 곱셈군 (\mathbb{Z}_{n}^{\ast}, \cdot_{n})이라 한다.

Theorem. 법 n 곱셈군은 유한아벨군이다.

법 n 곱셈군의 크기는 \phi(n)으로 이는 오일러의 파이 함수이다. p가 소수면 \phi(p) = p - 1이고, n이 합성수면 \phi(n) > \frac{n}{e^{\gamma} \ln \ln n + \frac{3}{\ln \ln n}}이 성립한다 (\gamma=0.577...오일러 상수)

Subgroups

군의 부분집합이 군에 주어진 연산에 군을 이룰 경우 이를 부분군이라 한다.

Theorem. (A nonempty closed subset of a finite group is a subgroup) 어떤 유한군의 공집합이 아닌 부분집합이 군에 주어진 연산에 대해 닫혀 있으면 그 부분집합은 부분군을 이룬다.

Theorem. (Lagrange’s theorem) 유한군 (S^{\prime}, \oplus)(S, \oplus)의 부분군이면 \lvert S^{\prime} \rvert | \lvert S \rvert이다.

Corollary. S’가 S의 진부분군이면 \lvert S^{\prime} \rvert \leq \frac{\lvert S \rvert}{2}이다.

Subgroups generated by an element

a에 의해 생성되는 부분군\langle a \rangle = \{a^{(k)} : k \geq 1\}으로 정의한다. 이 때 a가 \langle a \rangle생성하는 원소인 생성자라 한다. a의 S 내의 차수a^{(t)}가 항등원이 되는 최소 자연수 t이다.

Theorem. 유한군 S와 군 내 원소 a에 대해 a의 차수는 a에 의해 생성되는 부분군의 크기와 같다.

Corollary. 수열 a^{(i)}는 a의 차수 t를 주기로 가진다. 즉, a^{(i)} = a^{(j)}i \equiv j \mod t와 동치이다.

Corollary. 유한군 S의 항등원이 e라면 군 내의 원소 a에 대해 a^{\lvert S \rvert} = e이다.

31.4. Solving modular linear equations

모듈러 등식을 어떻게 풀까?

Theorem. 양의 정수 a, n에 대해 d = gcd(a, n)이면 \mathbb{Z}_{n} 내에서 \langle a \rangle = \langle d \rangle이고 \lvert \langle a \rangle \rvert = \frac{n}{d}이다.

Corollary. ax \equiv b \mod n의 해가 존재할 조건은 d = gcd(a, n)에 대해 d | b인 것이다.

Corollary. ax \equiv b \mod n는 해가 없거나, 아니면 d = gcd(a, n)에 대해 법 n에 대해 d개의 서로 다른 해가 존재한다.

Theorem. d = gcd(a, n)이고 어떤 정수 x’, y’에 대해 d = ax’ + ny’라 하자. d | b이면 ax \equiv b \mod nx_{0} = x^{\prime} \frac{b}{d} \mod n을 해로 갖는다.

Theorem. ax \equiv b \mod n의 해가 존재하고 x_{0}이 그 해라 하면 이 방정식은 i = 0, \cdots, d - 1에 대해 d개의 서로 다른 해 x_{i} = x_{0} + i \frac{n}{d}를 갖는다.

이제 모듈러 등식을 풀 수 있다.

MODULAR-LINEAR-EQUATION-SOLVER(a, b, n)
(d, x', y') = EXTENDED-EUCLID(a, n)
if d | b
    x_0 = x' (b / d) mod n
    for i = 0 to d - 1
        print (x_0 + i(n/d)) mod n
else
    print "no solutions"

Corollary. n > 1에 대해 gcd(a, n) = 1이면 ax \equiv b \mod n는 법 n에 대해 유일한 해를 갖는다.

b = 1일 경우 이 해를 곱셈에 대한 역수라 부른다.

Corollarly. n > 1에 대해 gcd(a, n) = 1이면 ax \equiv 1 \mod n는 법 n에 대해 유일한 해를 갖는다. 아니라면 해가 없다.

31.5. The Chinese remainder theorem

중국의 나머지 정리를 알아보자.

Theorem. (Chinese remainder theorem) 쌍별 서로소인 n_{1}, \cdots, n_{k}에 대해 n = n_{1} \cdots n_{k}라 하자. a \in \mathbb{Z}_{n}에 대해 a_{i} = a \mod n_{i}, a_{i} \in \mathbb{Z}_{n_{i}}이라 하자. 그러면 a \leftrightarrow (a_{1}, \cdots a_{k})은 일대일대응이며 \mathbb{Z}_{n}에 대한 연산 관계를 보존한다.

Corollary. 쌍별 서로소인 n_{1}, \cdots, n_{k}에 대해 n = n_{1} \cdots n_{k}라 하자. a_{1}, \cdots, a_{k} 에 대해 모듈러 등식 집합 x \equiv a_{i} \mod n_{i}의 해는 법 n에 대해 유일하다.

Corollary. 쌍별 서로소인 n_{1}, \cdots, n_{k}에 대해 n = n_{1} \cdots n_{k}라 하자. 모든 정수 x와 a에 대해 모든 i에 대해 x \equiv a \mod n_{i}를 만족하는 것은 x \mod a \mod n과 동치이다.

31.6. Powers of an element

원소의 거듭제곱의 성질을 알아보자.

Theorem. (Euler’s theorem) 1보다 큰 정수 n에 대해 모든 a \in \mathbb{Z}_{n}^{\ast}에 대해 a^{\phi(n)} \equiv 1 \mod n이 성립한다.

Theorem. (Fermat’s theorem) p가 소수면 a \in \mathbb{Z}_{p}^{\ast}에 대해 a^{p - 1} \equiv 1 \mod p이다.

g \in \mathbb{Z}_{n}^{\ast}의 차수가 \mathbb{Z}_{n}^{\ast}의 원소 수와 같으면 g를 \mathbb{Z}_{n}^{\ast}원시근 또는 생성자라 한다. \mathbb{Z}_{n}^{\ast}에 원시근이 존재하면 이를 순환군이라 한다.

Theorem. \mathbb{Z}_{n}^{\ast}을 순환군으로 만드는 n > 1의 값은 소수 p > 2와 양의 정수 e에 대해 2, 4, p^{e}, 2p^{e}이다.

g가 \mathbb{Z}_{n}^{\ast}의 원시근이고 a가 \mathbb{Z}_{n}^{\ast}의 원소일 때 g^{z} \equiv a \mod n을 만족시키는 z가 존재한다. 이를 a의 법 n에 대한 지수 또는 이산로그라 한다.

Theorem. (Discrete logarithm theorem) g가 \mathbb{Z}_{n}^{\ast}의 원시근이면 g^{x} \equiv g^{y} \mod nx \equiv y \mod \phi(n)과 동치이다.

Theorem. p가 홀수 소수고 e \geq 1이면 x^{2} \equiv 1 \mod p^{e}는 x = 1, x = -1의 해 2개만을 갖는다.

x^{2} \equiv 1 \mod n를 만족시키면서 x = 1, x = -1이 아니면 x를 법 n에 대한 1의 비자명 제곱근이라 한다.

Corollary. 법 n에 대한 1의 비자명 제곱근이 존재하면 n은 합성수이다.

Raising to powers with repeated squaring

정수 a의 n에 대한 모듈러 지수 연산을 생각할 수 있다. 이는 반복 제곱법으로 효율적으로 수행한다.

MODULAR-EXPONENTIATION(a, b, n)
c = 0
d = 1
let <b_k, ..., b_0> be the binary representation of b
for i = k downto 0
    c = 2c
    d = (d * d) mod n
    if b_i == 1
        c = c + 1
        d = (d * a) mod n
return d

31.7. The RSA public-key cryptosystem

RSA 공개키 암호화 과정을 알아보자.

Public-key cryptosystems

공개키 암호화 시스템에서는 각 참가자가 공개키비밀키를 가진다. Bob이 Alice에게 메시지 M을 전송하는 과정은 다음과 같다.

  • Bob이 Alice의 공개키 P_{A}를 얻는다.
  • Bob이 암호문 C = P_{A}(M)을 계산해 Alice에게 보낸다.
  • Alice는 비밀키로 S_{A}(C) = S_{A}(P_{A}(M)) = M을 복호화한다.

이의 검증은 다음과 같이 할 수 있다.

  • Alice는 메시지 M’에 대한 디지털 서명 \sigma = S_{A}(M')을 계산한다.
  • Alice는 Bob에게 (M', \sigma)을 보낸다.
  • Bob은 M' = P_{A}(\sigma)가 되는지 검증한다.

The RSA cryptosystem

RSA 공개키 암호화 알고리즘은 다음과 같다.

  1. p \neq q인 두 개의 큰 소수 p, q를 고른다. 각 1024 비트로 생각할 수 있다.
  2. n = pq를 계산한다.
  3. \phi(n) = (p-1)(q-1)과 서로소인 작은 홀수 e를 고른다.
  4. e의 법 \phi(n)에 대한 곱셈에 대한 역수 d를 계산한다.
  5. P = (e, n)을 RSA 공개 키로 게재한다.
  6. S = (d, n)을 RSA 비밀 키로 저장한다.

Theorem. (Correctness of RSA) RSA 방정식은 \mathbb{Z}_{n}에 대해 서로 역연산을 이룬다.

디지털 서명을 효율화하기 위해 충돌 저항 해시 함수 h를 같이 사용한다. 서명을 같이 배포하는 것은 공개 키 배포를 훨씬 더 쉽게 한다.

31.8. Primality testing

소수 여부를 체크하는 법에 대해 알아보자.

The density of prime numbers

소수 분포 함수 \pi(n)은 n 이하 소수의 수로 정의한다.

Theorem. (Prime number theorem) \lim_{n \to \infty} \frac{\pi n}{\frac{n}{\ln n}} = 1.

소수성 시험을 하는 간단한 방법은 \lfloor \sqrt{n} \rfloor 이하의 소수들로 하나하나 나눠 보는 시험 나눗셈이다. 물론 그것보다는 더 좋은 방법이 필요하다.

Pseudoprimality testing

합성수 n이 a^{n-1} \equiv 1 \mod n이면 법 a 유사소수라 한다. 유사소수 체크는 다음과 같다.

PSEUDOPRIME(n)
if MODULAR-EXPONENTIATION(2, n - 1, n) ≠ 1 (mod n)
    return COMPOSITE // definitely
else
    return PRIME // we hope!

법 a 유사소수 테스트로 합성수를 다 가려낼 순 없다. 모든 법 a에 대해 법 a 유사소수 테스트를 통과하는 합성수인 카미카엘 수가 존재하기 때문이다.

The Miller-Rabin randomized primality test

밀러-라빈 소수 테스트는 이를 보강한 테스트이다.

WITNESS(a, n)
let t and u be such that t ≥ 1, u is odd, and n - 1 = 2^t u
x_0 = MODULAR-EXPONENTIATION(a, u, n)
for i = 1 to t
    x_i = x_(i-1)^2 mod n
    if x_i == 1 and x_(i-1) ≠ 1 and x_(i-1) ≠ n - 1
        return TRUE
if x_t ≠ 1
    return TRUE
return FALSE

이를 적용해 밀러-라빈 테스트를 수행한다.

MILLER-RABIN(n, s)
for j = 1 to s
    a = RANDOM(1, n - 1)
    if WITNESS(a, n)
        return COMPOSITE // definitely
return PRIME // almost surely

Error rate of the Miller-Rabin primality test

밀러-라빈 테스트의 오판정율은 어떻게 될까?

Theorem. n이 홀수 합성수라면 n의 합성수성에 대한 증인수의 수는 최소 \frac{n-1}{2}이다.

증명은 n 이하 수의 쌍에 대한 허용가능성을 정의해 활용한다.

Theorem. 홀수 n > 2와 양의 정수 s에 대해 MILLER-RABIN(n, s)의 오판정률은 최대 2^{-s}이다.

31.9. Integer factorization

n의 소인수를 어떻게 구할까?

Pollard’s rho heuristic

다음의 휴리스틱을 사용한다.

POLLARD-RHO(n)
i = 1
x_1 = RANDOM(0, n - 1)
y = x_1
k = 2
while TRUE
    i = i + 1
    x_i = (x_(i-1)^2 - 1) mod n
    d = gcd(y - x_i, n)
    if d ≠ 1 and d ≠ n
        print d
    if i == k
        y = x_i
        k = 2k

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중