6. number theory

Fermat's Theroen (페르마 정리)

9^21 mod 11 이라면 얼마일까?

 

a와 p가 서로소 관계라면, a^(p-1) ≡ 1 (mod p)이다. 

또한 a^p ≡ a (mod p) 이다.

 

9^10 ≡ 1 (mod 11) 이므로, 9^20 ≡ 1 (mod 11)

9^21 mod 11 = (9^20 * 9) (mod 11) = 9^20 (mod 11) * 9 (mod 11) = 9 이다.

 

 

Euler Totient Function ø(n)

나머지로 나올 수 있는 집합, complete set of residues는 0 ... n-1  이다.

그 집합에서 n과 서로소인 집합, reduced set of residues도 있다.

예를 들어 n이 10인 경우,

complete set of residues = {0,1,2,...,9} 이고,

reduced set of residues = {1, 3, 7, 9} 이다.

여기서 reduced set of residues의 요소의 개수가 ø(n)이다.

 

ø(12) 라면, {1, 5, 7, 11} 이므로 ø(12) = 4 이다.

ø(15) 라면, {1, 2, 4, 7, 8, 11, 13, 14} 이므로 ø(15) = 8 이다.

ø(31) 라면, 31은 소수이므로 ø(31) = 30 이다. 소수는 모든 수에 대해 서로소이기 때문이다.

 

p가 소수라면, ø(p) = p-1이다.

p와 q가 소수라면, ø(pq) = (p-1)(q-1)이다.

 

따라서 ø(21) = ø(3*7) = (3-1)(7-1) = 12 이다.

 

 

Euler's Theorem

10^25 mod 21의 경우, 21이 소수가 아니기에 페르마 정리를 적용하지 못한다.

 

오일러 법칙에 따라, 만약 a와 n이 서로소라면, a^ø(n) ≡ 1 (mod n)이다.

 

따라서 10^ø(21) ≡ 1 (mod 21)이고,

ø(21) = ø(3*7) = 12이므로,

10^12 ≡ 1 (mod 21), 10^24 ≡ 1 (mod 21)

10^25 mod 21 = 10^24 * 10 mod 21 = 1*10 = 10이다.

 

7^25 mod 21의 경우 7과 21이 서로소가 아니므로 위 내용을 그대로 적용하지 못한다.

 

만약 n이 서로 다른 소수의 곱이라면, r ≡ s (mod ø(n))이고, a^r  ≡ a^s (mod n)이다.

또한, a^(ø(n)+1) ≡ a (mod n)이다.

 

따라서 7^25 mod 21의 해를 구하면, 21은 3*7이다.

3 ≡ 7 (mod ø(21)), 7^3 ≡ 7^7 (mod 21)이며,

7^13 ≡ 7 (mod 21)이 된다.

그러므로, 7^26 mod 21 = 7^25 * 7 mod 21 = 1 * 7 = 7 이다.

 

이 이론은 RSA에 사용된다.

 

 

Primality Testing

소수인지 아닌지 판별하는 방법.

sieve 알고리즘은 소수를 발견했을 때 그 소수의 곱(i^2, i^2+i, i^2+2i ...)들을 전부 소거한다. 이 방법은 매우 느리다.

i^2부터 제거하는 이유는, (i-1)i 이하는 앞에서 이미 제거되었다. i가 소수이기 때문이다.

 

statistical primality는 확률적으로 검사하는 방법이다.

확률의 리스크를 없애기 위해, 얻은 값을 소수로 가정하고 계산하는 방법으로 값이 다르면 소수가 아니게 된다.

=> 소수가 아니라고 하면 100% 확률로 소수가 아니다. - false positive

=> 소수라고 한다면 확실하진 않다. - not false negative

 

이러한 알고리즘이 Miller Rabin Algorithm이다.

 

 

Miller Rabin Algorithm

임의의 p에 대하여, 어떤 a에 대해 a^(p-1) ≡ 1 (mod p), 페르마 정리가 성립한다면 소수일 가능성이 있다.

 

n이 소수인지 판별한다고 하자.

(n-1) = 2^k * q를 성립하는 k와 q를 찾는다. (k>0,  q%2 = 1)

1과 n-1 사이의 랜덤한 정수 a를 고른다.

 

a^(2^k*q) ≡ 1 mod n이 성립하면 소수일 가능성이 있다. (n-1 이 2*k * q이기 때문이다.)

=> a^(2^k*q)-1 ≡ 0 mod n 를 인수분해 하면,

a^(2^k*q)-1 = (a^(2^(k-1)*q) + 1)(a^(2^(k-2)*q) + 1) ... (a^q+1)(a^q - 1) 이다.

분해된 모든 값들 중 mod n 값이 0인 것이 있다면 소수일 가능성이 있다.

 

만약 알고리즘의 결과가 합성수라면 절대 소수가 아니다.

만약 결과가 소수라면 소수일 가능성이 있다. 이 것을 t번 반복하면 그 확률은 1-1/4^t이다.

만약 10번 반복한다면 그 확률은 0.99999보다 높다.

 

특정 범위 내에서 확실하게 소수를 판별할 수 있다.

n<2^64라면, a = {2,3,5,7,11,13,17,19,23,29,31,37} 를 통과하면 100% 소수이다.

 

 

Prime Distribution

소수는 대략적으로 ln(n) 정수마다 발생한다. 여기서 n은 찾고자 하는 범위이다.

단, 2를 제외한 모든 짝수는 합성수이므로, 0.5ln(n)으로 탐색할 수 있다.

예를 들어, 2200 근처에 소수를 찾는다고 가정하자. 

평균적으로 0.5 * ln(2200) => 69개의 수를 탐색했을 때 소수를 찾을 수 있다.

 

 

Chinese Remainder Theorem (CRT)

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

moduler number, m값이 모두 서로 서로소일 때, 3*5*7 아래에서 위 식을 만족하는 x는 단 한 개이다.

 

여기서 3*5*7를 M이라고 나타내면,

M = 3*5*7, CRT를 사용하여 각각의 m_i에 대해 따로 연산을 수행할 수 있다.

계산 비용이 일반적으로 연산을 수행해야하는 숫자의 크기에 비례하기에, 더 효율적으로 계산할 수 있다.

 

A mod M을 계산한다고 하자,

M = m_1 * m_2 * ... * m_k로 나타낼 수 있다. m_i들은 서로에 대해 서로소이다. 그러한 m들은 미리 구해놓아야 한다.

먼저 A를 각 m_i로 나눈 나머지, 즉 a_i = A mod m_i 를 따로 계산한다.

각 c_i는, M_i = M/m_i 라 할 때, c_i = M_i * (M_i^-1 mod m_i)의 곱으로 계산된다.

그러한 모든 a_i와 c_i를 합친 값의 mod M이 답이 된다.

int A, M, m[k];
sum = 0;
for(int i=0; i<k; i++){
	a[i] = A % m[i];
    M_i = M / m[i];
    c_i = M_i * mul_inv(M_i, m[i]);
    sum = sum + a[i] * c[i];
    if(sum >= M) sum -= M;
}

 

 

Primitive Roots

오일러 정리에 따르면 n과 어떤 정수 a에 대해 둘이 서로소이면 a^ø(n) = 1이 성립된다.

 

a^m ≡ 1 (mod n), gcd(a, n) = 1 라고 고려했을 때,

-> m = ø(n)일 수도 있지만, 더 작을 수도 있다.

-> 한 번 m 값에 도달하면, 지수의 값이 반복된다.

 

만약 , a의 최소 지수가 m = ø(n)이면, a를 원시근이라 한다. 원시근은 해당 모듈러 아래에서 군을 생성한다.

원시근을 찾는 것은 상대적으로 어렵다.

 

위 이미지는 mod 19에서의 표이다.

a=2,3,10,13,14,15일 때 m=ø(19)에서 1이 나타난다. 따라서 a=2,3,10,13,14,15가 각각 원시근이 된다.

 

 

Discrete Logarithms (이산 로그)

3^4 mod 19 = x

여기서 x를 구하는 것은 쉽다. square multiplication을 통해 더 효율적으로 알아낼 수 있다.

square multiplication이란, 효율적인 거듭제곱 연산을 위한 것으로,

a^2015의 경우, 지수를 2진수로 나타내면 11111011111이다.

y = a^1 * a^2 * a^4 * a^8 * a^16 * a^64 * a^128 * a^256 * a^512 * a^1024 로 나타낼 수 있다.

 

y = a^x mod n을 구하는 코드는 다음과 같다.

y = 1;
while(x>0){
	if(x&1){
    	y = (y * a) % m;
   	}
    a = a * a % m;
    x = x >> 1;
}

 

 

그러나, 3^x mod 19 = 4, x = log_3(4) (mod 19)에서 x를 구하는 것은 어렵다.

이산 로그 문제는 이 x를 찾는 것이 목표이다.

 

i = log_a(b) (mod p)라고 할 때,

a가 원시근이면 로그 값은 항상 존재한다. 그렇지 않을 경우 존재하지 않을 수도 있다.

 

예를 들어, x = log_3(4) (mod 13)의 해는 존재하지 않는다. 3이 13에 대한 원시근이 아니기 때문이다.

 

x = log_2(3) mod 13의 해는 4이다. 2는 13에 대한 원시근이고, 4를 대입하면 해가 맞는다.

결국 가능한 모든 값을 대입해야하기 때문에 큰 숫자에 대해서는 풀이가 어렵다.