1. Algorithms with numbers

숫자와 관련된 기초적 알고리즘은 소인수분해와 소수 판정이 있다. 소인수분해는 어렵다. 소수인지 판정하는 것은 상대적으로 쉽다. 이와 관련된 알고리즘을 알아보자.

1.1. Basic arithmetic

1.1.1. Addition

더하는 법을 알아보자. 3개의 한 자리 수를 더하면 최대 두 자리인 것은 명백하다. 이끌이수가 언제나 한 자리이기 때문이다. 이진 숫자 2개에 대해서는 얼마나 걸리나? O(n)이다. 더 빠른 알고리즘이 존재하나? 그렇지 않다. 하드웨어에서는 단어 길이 이하의 숫자 2개에 대해서는 O(1)로 더하지만 그건 일단 제껴 두자.

1.1.2. Multiplication and division

곱에 대해서도 간단하다. 이는 O(n^{2})이다. 하나는 2로 나누고 하나는 2를 곱하는 알고리즘도 존재한다.

function multiply(x, y)
Input: Two n-bit integers x and y, where y ≥ 0
Output: Their product
if y = 0: return 0
z = multiply(x, floor(y / 2))
if y is even:
    return 2z
else:
    return x + 2z

이도 역시 O(n^{2})이다. 더 잘할 수 있을까? 있다. 나중에 소개한다. 나눗셈은 어떻게 할까?

function divide(x, y)
Input: Two n-bit integers x and y, where y ≥ 0
Output: The quotient and remainder of x divided by y
if x = 0: return (q, r) = (0, 0)
(q, r) = divide(floor(x / 2), y)
if x is odd: r = r + 1
if r ≥ y: r = r - y, q = q + 1
return (q, r)

1.2. Modular arithmetic

제한된 범위 내에서의 정수만이 필요할 때가 있다. 이를 위해 모듈러 연산이 있다. 이는 다음으로 정의된다: x ≡ y (mod N) ↔ N | (x – y). 이는 동치류를 정의한다. 동치 관계를 만족하기 때문이다. 또한 이는 합과 곱에 대해 보존된다.

1.2.1. Modular addition and multiplication

모듈러 덧셈은 자연스럽게 정의된다. 모듈러 곱셈도 마찬가지다. 모듈러 나눗셈은 좀 어렵다. O(n^{3})이다. 모듈러 연산을 암호론에 활용하기 위해서는 모듈러 지수승이 필요하다.

1.2.2. Modular exponentation

x^{y} \mod N을 어떻게 구할까? 이진 승수들의 모듈러 값을 구하면 된다.

function modexp(x, y, N)
Input: Two n-bit integers x and N, an integer exponent y
Outout: x^y mod N

if y = 0: return 1
z = modexp(x, floor(y / 2), N)
if y is even:
    return z^2 mod N
else:
    return x * z^2 mod N

이는 O(n^{3})이다.

1.2.3. Euclid’s algorithms for greatest common divisor

최대공약수를 어떻게 구할까? 다음을 이용한다: 양의 정수 x ≥ y에 대해서는 gcd(x, y) = gcd(x mod y, y). 이를 이용하면 다음과 같다.

Euclid(a, b)
Input: Two integers a and b with a ≥ b ≥ 0
Output: gcd(a, b)

if b = 0: return a
return Euclid(b, a mod b)

이는 재귀 알고리즘이다. 또한 a ≥ b이면 a mod b < a / 2라는 사실을 이용하면 O(n^{3})이 됨을 알 수 있다.

1.2.4. An extension of Euclid’s algorithm

이를 확장해 모듈러 나눗셈을 할 수 있다. 다음을 이용한다: d가 a, b를 모두 나누고 어떤 정수 x, y에 대해 d = ax + by가 된다면 d = gcd(a, b)이다. 이를 이용하면 다음과 같다.

extended-Euclid(a, b)
Input: Two posoitive integers a and b with a ≥ b ≥ 0
Output: Integers x, y, d such that d = gcd(a, b) and ax + by = d

if b = 0: return (1, 0, a)
(x', y', d) = extended-Euclid(b, a mod b)
return (y', x' - floor(a / b)y', d)

이는 정확하다.

1.2.5. Modular division

모듈러 나눗셈은 어떻게 정의할까? ax ≡ 1 (mod N)이면 x를 a의 모듈러 N에 대한 역수라 한다. 이런 x는 최대 하나밖에 없다. gcd(a, N) ≠ 1이면 존재하지 않고 아니면 존재한다. 이는 O(n^{3})이다.

1.3. Primality testing

다음이 성립한다: p가 소수면 1 ≤ a < p에 대해 a^{p-1} \equiv 1 \mod p이다. 이를 이용해 소수를 판정하면 다음과 같다.

function primality(N)
Input: Positive integer N
Output: yes/no

Pick a positive integer a < N at random
if a^(N - 1) ≡ 1 (mod N):
    return yes
else:
    return no

이는 완벽하지는 않다. 정말 극히 드문 경우에 반례가 존재한다. 또한, a < N 중 하나에 대해서 성립하면 a < N 중 최소 절반에 대해서도 성립해야 한다. 이를 이용하면 100번 테스트하면 테스트가 틀릴 확률은 최대 2^{-100}이다. 이를 이용하면 반복 테스트를 다음과 같이 만들 수 있다.

function primality2(N)
Input: Positive integer N
Output: yes/no

Pick a positive integer a_1, ..., a_k < N at random
if (a_i)^(N - 1) ≡ 1 (mod N) for all i = 1, ..., k:
    return yes
else:
    return no

1.3.1. Generating random primes

무작위 소수를 생성하려면 어떻게 할까? π(x)가 x 이하의 소수의 수라고 하면 \lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1이 성립한다. 그러므로 무작위 소수 추출 알고리즘의 평균 기대 시간은 n비트 시 O(n)이다. 대개 a = 2를 택한다.

1.4. Cryptography

RSA 암호화 알고리즘을 알아보자. 이는 공개키와 비밀키로 이루어진다.

1.4.1. Private-key schemes: one-time pad and AES

AES 알고리즘은 비밀키 일회용 패드를 사용한다. 이는 무식한 시도 이외에 깨트릴 방법이 알려지지 않았다.

1.4.2. RSA

RSA는 공개키와 비밀키를 사용한다. 다음을 이용한다: 두 소수 p, q에 대해 N = pq면 (p – 1)(q – 1)과 서로소인 임의의 e에 대해 x \to x^{e} \mod N은 전단사함수고, 역함수는 구하기 쉽다. 또한, N, e, y = x^{e} \mod N이 주어져도 x를 계산적으로 판정할 수 없다.

1.5. Universal hashing

해싱에 대해 알아보자.

1.5.1. Hash tables

해시 함수는 적당한 양수로 키를 보내는 함수고 해시 테이블은 이를 이용한 자료구조이다.

1.5.2. Families of hash functions

좋은 해시 함수를 설계하는 것은 매우 어렵다. 해시 함수에서 계수를 0 ~ n – 1 중 무작위로 선택했을 때 해시 충돌 확률은 1 / n이다. 임의의 서로 다른 두 데이터 x, y에 대해, \mathcal{H} 내의 모든 해시 함수 중 \frac{\lvert \mathcal{H} \rvert}{n}개가 x, y를 같은 버킷으로 보낸다. n은 버킷의 수. 이를 이용해 전역적 해싱을 설계할 수 있다.

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중