Divisibility (가분성)
b | a
: b / a
: a = m * b
: b는 a의 약수이다.
Greatest Common Divisor (GCD)
gcd(a,b) = max(k, such that k | a and k | b)
0은 모든 수를 약수로 갖음.
a = k x m, b = k x n
k는 a의 약수이다, k는 b의 약수이다.
그렇기에 max(k, k | a and k | b)
-> k의 최대 공약수
0은 모든 수의 배수.
-> gcd(a,0) = |a|
-> gcd(0,0) = 0
Euclidean Algorithm
gcd(a,b) = gcd(b,r)
ex) gcd(1066,904) = gcd(2,0)
gcd(2,0) = 2 이다. 결국 앞에꺼도 1066,904 최대공약수는 2이다. (이거 증명하는 과정 3강(1))Extended Euclidean Algorithm
ax + by = d = gcd(a,b)
a와 b의 최대공약수인 d를 만족하기 위한
a x 임의의 x 와 b x 임의의 y가 반드시 존재한다. ex) gcd(161,28) = 7 일때
-> s x 161 + t x 28 = 7이다.
여기서 보면 s = -1, t = 6이다.
즉, -1 x 161 + 6 x 28 = 7 이다.
Modular Arithmetic
Complete set of residues Zn의 원소의 개수는 n이고 값들은 {0 ~ n-1}
: 어떤 수를 n으로 나눴을때 나올 수 있는 집합이다.
Congruent Modulo n (합동)
: 나눴을때 값이 같은거
ex) 73 = 4 (mod 23)
: 73을 23으로 나눴을때 나머지가 4이고, 4를 23으로 나눴을때도 나머지가 4이다.
ex) 21 = -9(mod 10) 음수 모듈러 법칙 a ≡ b (mod n) ⇔ n ∣ (a−b) = 참
a ≡ 0 mod n이면 n | a 이다.모듈러 연산
Phi Function
N이 주어졌을때 Zn(N으로 나눴을때 나오는 원수들의 집합), N과 서로소인 수의 개수를 나타내는것이 Phi 함수이다.
Phi(1) = 1
Phi(p) = p - 1 (P가 소수인 경우)
: P로 나눴을 때 생기는 원소들 P와 서로소인 개수 0 빼고 P-1개
ex)
n = p x q 인 경우 Phi(pq) = Phi(p) x Phi(q)이다.
-> 증명: Zn = {0,1,2, .. , (pq-1)}, p의 배수: p,2p,3p,...,(q-1)p로 원소의 개수는 p-1, q의 배수: q,2q,3q,...,(p-1)q로 원소의 개수는 q-1개.
전체 pq - (p-1) - (q-1) -1(0) = (p-1) x (q-1) = Phi(p) x Phi(q)
4같은 경우 Z4 = {1,2,3} 이지만 2랑은 서로소가 아니므르 Phi(4) = 2 이다.
Naive Solution (소수 판별법)
103의 루트를 씌어 나온 n까지 2~n 까지 소수로 나누어 떨어지는지 확인하고 나누어 떨어지지 않는다면 103은 소수이다.
Chinese Remainder Theorem(CRT)
pairwise relatively:
N = n1 x n2 x n3 .. x nk 중에 아무거나 2개 뽑아서 gcd 했을때 모두 1이다. 즉 서로소이다.
그럼, x ≡ 2 (mod3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) 인경우를 보자.
N = 3 x 5 x 7 = 105
N1 = 105 / 3 = 35, N2 = 105 / 5 = 21, N3 = 105 / 7 = 15
y1 = 35의 역원 mod 3 = 2, y2 = 21의 역원 mod 5 = 1, y3 = 15의 역원 mod 7 = 1이다.
이때 x = 2 x 35 x 2 + 3 x 21 x 1 + 2 x 15 x 1 이다.
-> 233 (mod 105) ≡ 23 (mod 105)
✅ 233 mod 105 = 23 임.
Discrete Logarithms Problem(DLP)
y = g^x mod p
y,g,p가 주어졌을 때 x를 찾는 문제가 DLP문제이다.
ex) y = 32, g = 2 이면 우린 당연히 log32를 통해 x가 5인것을 알 수 있지만 여기서는 mod 연산이 있음으로 연산 결과가 계속 커지는 것이 아닌 커졌다 작아졌다 반복을 하게 된다. 그렇기에 이 문제를 푸는 방법은 Bruteforce 공격이기에 문제를 해결하기 어렵다.
