8. 모듈러/정수론 정리

GCD, Euclid Algorithm

gcd(a, b) = gcd(b, a%b) 를 기반으로 함.

 

Modular Arthmetic

a mod b = (a+kb) mod b, k는 임의의 정수

x*y mod b = (x mod b * y mod b) mod b

 

Extended Euclid Algorithm

유클리드 알고리즘으로 나온 최대공약수로부터 역추적하며 gcd(a, b) = ax + by가 되는 x와 y를 찾음.

int extended_gcd(int a, int b, int *x, int *y)
{
	if (b == 0)
	{
		*x = 1;
		*y = 0;
		return a;
	}
	int x1 = *x;
	int y1 = *y;
	int gcd = extended_gcd(b, a % b, &x1, &y1);
	*x = y1;
	*y = x1 - (a / b) * y1;
	return gcd;
}

위는 재귀를 이용한 코드. b == 0일 때 gcd(a', b') = ax = a 이므로 x=1, y=0

그로부터 재귀의 깊이만큼 이전 x, y값 x1, y1으로부터 x = y1; y=x1 - (a//b)*y1을 반복한다.

x, y에 대입되는 값은, gcd 함수 인자에 들어가는 a, b값과 같다. (a%b = a-(a//b)*b)

 

int extended_gcd(int a, int b, int *x, int *y)
{
    int x0 = 1, y0 = 0;
    int x1 = 0, y1 = 1;

    while (b)
    {
        int q = a / b;

        int tmp = a; a = b; b = tmp % b;

        tmp = x0 - q * x1; x0 = x1; x1 = tmp;

        tmp = y0 - q * y1; y0 = y1; y1 = tmp;
    }

    *x = x0;
    *y = y0;

    return a;
}

위는 반복문으로 구현된 코드, 먼저 gcd로써 b가 0이 될 때까지 a = b, b = a%b를 반복한다.

여기서 x0, y0은 현재 값, x1, y1은 이전 값이다. 다만 재귀일때와 방향이 다르기에, x와 y의 업데이트 방법이 다르다.

 

여기서, b>1 인동안 반복한 다음, b==1이면 a를 반환하는 방법으로 a의 mod b에 대한 역을 구하는 함수를 작성할 수도 있다.

확장 유클리드 호제법의 x, y값은 gcd(a,b)가 1일 때, x = a^-1 mod b, y = b^-1 mod a 이기 때문이다.

 

 

GF(2^n), Irreducible Polynomial

GF(2^n)에서의 연산은 연산 후 기약다항식으로 나머지연산을 취해준다.

 

GF(2^3)에서 기약다항식은 x^3 + x + 1 (1011) 이다.

GF(2^8)에서 기약다항식은 x^8 + x^4 + x^3 + x + 1 (100011011)이다.

GF(2^16)에서 기약다항식은 x^16 + x^5 + x^3 + x + 1 (10000000000101011) 이다.

 

uint8_t multiply(uint8_t x) {
	return ((x<<1) ^ ((x>>7) & 1 ? 0x1B : 0)); 
}

위 코드는 GF(2^8)에서 x에 2를 곱한 값을 반환한다.

x를 좌측 쉬프트함으로 2를 곱하는데, 만약 x의 최상위비트가 1이였다면 나머지연산을 위해 기약다항식을 더해준다. (XOR)

참고) 0x1B = 0b00011011

 

 

Fermat's Theoren (페르마 정리)

a와 p가 서로소 관계일 때,

 -> a^(p-1) ≡ 1 (mod p)

 -> a^p ≡ a (mod p)

 

Euler Totient Function ø(n)

ø(n) : mod m에서 나올 수 있는 요소 중 m과 서로소인 요소의 개수

n이 소수라면, ø(n) = n-1

n=pq일 때 p와 q가 소수라면, ø(n) = (p-1)(q-1)

 

 

Euler's Theorem

a와 n이 서로소라면,

a^ø(n) ≡ 1 (mod n)

 

mod n에서 n이 서로 다른 소수의 곱, n=r*s 라면,

r ≡ s (mod ø(n))

a^r  ≡ a^s (mod n)

a^(ø(n)+1) ≡ a (mod n)

 

 

Miller Labin

확률적 소수판별법이다. 합성수는 정확히 판별, 소수는 확률적으로 판별한다.

 

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

1. n을 n-1 = 2^s * d로 분해 (d is odd, s>0)

2. 무작위 a 선택 (2 <= a <= n-2)

3. x = a^d mod n 계산, x==1 or x==n-1 이면 소수일 수도 있으므로 다시 2번으로 넘어감.

4. s-1번 반복하면서 x = x^2 mod n을 계산. 반복 중 모든 x가 n-1이 아니라면 n은 합성수임.

 

t번 반복하면 소수일 확률은 1-0.25^t 이다.

 

n < 2^64일 때, a = [2,3,5,7,11,13,17,19,23,29,31,37] 만 검사하면 확실하게 소수 판별 가능

 

 

Chinese Remainder Theorem

x ≡ A mod M 에서, M을 m_1 * m_2 .. * m_k 로 표현했을 때,

m_i 끼리 전부 서로소라면, M 아래에서 식을 만족하는 x는 단 한 개이다.

 

CRT

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 += a_i * c_i;
	sum %= M;
}

 

 

Primitive Roots

a^m ≡ 1 (mod n), gcd(a, n) = 1일 때, m이 ø(n)이라면 a를 mod n에 대한 원시근이라고 한다.

원시근은 해당 모듈러 아래에서 군을 생성한다.

 

 

Square Multiplication

y = a^x mod n 이라고 할 때, a, x, n이 주어졌다면,

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

 

 

Discrete Logarithms

y = a^x mod n 이라고 할 때, y, a, n이 주어졌다면,

x = log_a(y) mod n 이라고 표현할 수 있다.

a가 mod n에 대한 원시근이라면 x가 항상 존재한다.

x는 모든 값을 대입해봐야 알 수 있다.