07. 오일러의 파이함수(Euler's Totient Function)

● 목적

- 임의의 자연수 n을 선택 했을 때, 1~n사이에 있는 수 중에서 n과 서로소인 수의 개수를 쉽게 구한다. (ex. RSA에서 사용)

● 용어정의

- ф(p): 1~p사이에 있는 수 중에서 p와 서로소인 수의 개수. (p는 양의 자연수)

● 공식

1) p가 소수일 때, ф(p^k)=p^k*(1-1/p)
2) p와 q가 서로 다른 소수 일때, ф(p*q)=ф(p)*ф(q)

2) p와 q가 서로소 일때, ф(p*q)=ф(p)*ф(q)*(d/ф(d)), 단, d=gcd(p,q)

3) m=p1^k1*p2^k2*p3^k3.... 라고 가정 할 때 ф(m)=m*(1-1/p1)*(1-1/p2)....... (단, p1,p2...는 서로 다른 소수)

● 증명 1) [ф(p^k)=p^k*(1-1/p)]

① p가 소수일 때, 1~p의 수 중에서 p와 서로소인 수의 개수는 p-1이다. 즉, ф(p) = p-1

② 1~p^k의 수 중에서 p^k와 서로소가 아닌 수는 소수p의 배수 뿐이다. (ex. 1~3^5의 수 중에서 3^5와 서로소가 아닌 수는 3, 6, 9, 12, 15 이다.)

③ 1~p^k의 수 중에서 p^k와 서로소가 아닌 수는 p, p*2, p*3, p*4... p^k이다.

④ p^k개의 수 중에서 p^k와 서로소가 아닌 수의 개수는 p^(k-1)개이다.

∵ p*1 [1개], p*2 [2개], p*3 [3개], p*4 [4개]... p*p^(k-1) [p^(k-1)개]

⑤ ф(p^k)=p^k-p^(k-1)=p^k*(1-1/p)

∴ ф(p^k)=p^k*(1-1/p)

● 증명 2) [ф(p*q)=ф(p)*ф(q)]

① 1~p*q의 수의 개수는 p*q이다.

② 1~p*q의 수 중에서 p와 서로소가 아닌 수의 개수는 q개 이다.

∵ p*1 [1개], p*2 [2개]. p*q [q개]

③ 1~p*q의 수 중에서 q와 서로소가 아닌 수의 개수는 p개 이다.

∵ q*1 [1개], q*2 [2개]. q*p [p개]

④ 1~p*q의 수 중에서 p와 q가 공통으로 갖게되는 공배수는 p*q으로 1개이다.

∵ p*q [1개]

⑤ 전체 수 에서 서로소가 아닌 수를 뺀다면, p*q-(p+q-1)=(p-1)(q-1)

⑥ p가 소수일 때, ф(p)=p-1 이었다는 것을 상기시켜보자.

⑦ ф(p*q)=(p-1)(q-1)=ф(p)ф(q)

∴ ф(p*q)=ф(p)*ф(q), (단 p와 q는 소수?????????????????????????????????????, 원래는 p와q는 서로소 여야만 한다. 하지만 p가 소수라는 가정을 하지 않으면 ф(p)=p-1 라는 가정을 사용할 수 없다. )

● 증명 3) [ф(m)=m*(1-1/p1)*(1-1/p2)....... ]

● 예제

① 36보다 작은 수 중에서 36과 서로소인 수의 개수 구하라.??????????????????

ф(36)

=ф(2^2*3^2)

=ф(2^2)*ф(3^2)

=2^2(1-1/2)*3^2(1-1/3)

=12

② ф(x)=12 를 만족하는 모든 수를 구하라.??????????????????????????????????

ф(x)=1*12

=(2-1)*(13-1)

=ф(2)*ф(13)

=ф(26)

ф(x)=2*6

=(3-1)*(7-1)

=ф(3)*ф(7)

=ф(21)

ф(x)=3*4

=(4-1)*(5-1)

=ф(4)*ф(5)

=ф(20)

ф(x)=2*2*3

=(3-1)*(3-1)*(4-1)

=ф(3)*ф(3)*ф(4)

=ф(36)

x=20, 21, 26, 36

06. 중국인의 나머지 정리

todo

05. 확장된 유클리드 알고리즘(Extended euclidean algorithm)

● 활용
- 공개키 암호화 알고리즘에서 비밀키를 알아내기 위해 사용.
- 공개키 암호화 알고리즘의 가장 어려운 부분은 큰 두 소수의 곱을 가지고, 두개의 소수를 유추해 내는 것이다.
- 즉, p*q=N 일 때, p와 q의 값을 알 때, N은 쉽게 구할 수 있다. 하지만, N을 값 만으론 p와 q를 유추해 내기 어렵다.

● RSA 공개키/비밀키 생성방법 요약
① 두 개의 서로 다른 소수 p, q 선택.
② p * q를 공용키로 선택
③ (p - 1)(q - 1)의 값과 서로 소인 임의의 정수 e를 선택해서 공개키로 사용.
④ e와 서로소인 d를 선택해서 비밀키로 사용. ed≡1 (mod (p-1)*(q-1))
∵ 확장된 유클리드 알고리즘을 사용해서 비밀키를 생성 할 수 있다.

● 정의
- ap + bq = GCD(p, q) 식에서 a와 b를 구 할 수 있다.

● 예제
① 두 개의 서로 다른 소수 p, q 선택. p = 17, q = 37
② (p - 1)(q - 1)과 서로소인 임의의 정수 e를 선택. e = 31
③ GCD((p - 1)(q - 1), 31) => GCD(576, 31)
GCD(576, 31) => 576 = 31 * 18 + 18
GCD(31, 18) => 31 = 18 * 1 + 13
GCD(18, 13) => 18 = 13 * 1 + 5
GCD(13, 5) => 13 = 5 * 2 + 3
GCD(5, 3) => 5 = 3 * 1 + 2
GCD(3, 2) => 3 = 2 * 1 + 1
=>
① 1 = 3 - 2
= 3 - (5 - 3) => 2 * 3 - 5
= 2 * ( 13 - 5 * 2 ) - 5 => 2 * ( 13 ) - 5 * 5
= 2 * 13 - 5 * ( 18 - 13 ) => -5 * ( 18 ) + 7 * 13
= -5 * 18 + 7 * ( 31 - 18 ) => 7 * 31 - 12 * ( 18 )
= 7 * 31 - 12 * ( ( 576 - (31 * 18) ) ) => -12 * 576 + 223 * 31
② -12 * 576 + 223 * 31에서 사고를 확장해 보았을 때, 223 * 31≡1(mod 576)을 알 수 있다. 576은 (p-1)(q-1)의 값.
※ 증명
ⓐ a≡r (mod p) 이면. a = p*x + r 양변에 p를 더해 준다면 => a + p = p* (x + 1) + r 로 나머지 값은 변화가 없음을 알 수 있다.
ⓑ -12 * 576은 무시할 수 있다.
③ 이제 비밀키 선택 알고리즘에서 ed≡1 (mod (p-1)*(q-1)) d의 값을 구할 수 있다. 223 * 31≡1(mod 576)
∵ 비밀키는 223

04. 유클리드 호제법(Euclidean algorithm)

● 정의
- A = BQ + R 일 때, A와B의 최대공약수, B와 R의 최대공약수는 같다.

● 증명
① gcd(A, B)를 G라고 가정한다. ( A = aG, B=bG )
② A = BQ + R에 각각의 변수를 대응 시킨다. ( aG = bGQ + R )
③ (a - bQ)G = R 로 변환이 가능하며 A, B, R 은 모두 G의 배수라고 말할 수 있다. B=bg, R=(a - bQ)G 이므로 b와 (a - bQ)가 서로소이고 B와 R의 최대공약수가 G가 된다.
※ 증명
ⓐ b와 (a - bQ)가 서로소가 아니라고 가정한다. b = dn, (a - bQ ) = dm 그리고 이 식이 거짓임을 증명함으로써 b와 (a - bQ)가 서로소임을 증명한다.
ⓑ (a - (dn)Q) = dm => (a - dnQ) = dm => a = dm + dnQ => a = d( m + nQ )
ⓒ a = d( m + nQ ), b = dn 이므로 a와 b가 d 라는 공약수를 가지게 된다. 이것은 a와 b가 서로소라는 앞의 가정에 모순이 되기 때문에 b와 (a - bQ)는 서로소라는 것이 증명된다.

● 예제
Q. GCD(206, 40)을 구하라.

A. 2

GCD(206, 40) = GCD(40, 6)
= GCD(6, 4)

= GCD(4, 2)
= GCD(2, 0)
= 2

03. 페르마 테스트(Fermat's test)

todo

02. 페르마의 소정리(Fermat's little theorem)

● 정의
- p가 소수일 때 p와 서로소인 a에 대해서 a^(p-1)≡1(mod p)가 성립한다.
- a^(p-1)≡1(mod p) → a^(p)≡a(mod p) 합동(Congruence)참조

● 증명
① A={1,2,3,4,5......(p-1)} 집합A를 정의한다.
② p가 소수이기 때문에, 집합A의 원소를 각각 p로 나눈 나머지는 모두 다르다.
③ B={1*a, 2*a, 3*a, 4*a, 5*a.......(p-1)*a} 집합B를 정의한다.
④ 집합B의 원소를 각각 p로 나눈 나머지는 모두 다르다.
※ 증명
ⓐ B의 원소 중 2개를 선택한다. (각각 a*m, a*n으로 정의한다. m≠n )
ⓑ a*m과 a*n을 p로 나눈 나머지가 같다고 가정한다. a*m≡a*n(mod p) → 가정이 맞지 않는다는 것을 증명하기 위해서
ⓒ a*m≡a*n(mod p) → (a*m) - (a*n)≡0(mod p)
Ⅰ. 합동(Congruence)에서 a≡b(mod p), c≡d(mod p)일 때, a+c≡b+d(mod p)라는 것을 증명했다.
Ⅱ. a*m≡r(mod p), a*n≡r(mod p) (ⓑ가정에 의해서 나머지가 r로 같다. )
Ⅲ. a*m+ -(a*n)≡r+ -(r)(mod p)
ⅳ. 즉, (a*m)-(a*n)≡0(mod p)가 성립한다.
ⓓ a(m*n)≡0(mod p)
ⓔ p는 a(m*n)의 배수라는 결과가 나온다. 따라서 p가 소수라는 전제에 위된다.
∵ a*m과 a*n을 p로 나눈 나머지는 같지 않다. 즉 집합B의 원소를 각각 p로 나눈 나머지는 모두 다르다.
⑤ 집합A의 원소를 p로 나눈 나머지와 집합B의 원소를 p로 나눈 나머지는 같다.
⑥ 따라서 집합A의 원소를 모두 곱한 값의 나머지와 집합B의 원소를 모두 곱한 값의 나머지는 같다.
⑦ (p-1)!≡(p-1)!*a^(p-1)(mod p)
∵ a^(p-1)≡1(mod p)

● 예제
Q. 10^(6015)+10^(1203)-10^(15)-10^(k)가 2005의 배수가 될 때, k의 최소값은? (KMO)

A. k = 3

2005의 배수가 된다는 말은 401의 배수가 된다는 말로 바꿀 수 있다. ( 2005 = 15 * 401 )
6015=401*15, 1203=401*3
10^(401)≡10(mod 401)
10^(401*15))≡10^(15)(mod 401)
10^(401*3))≡10^(3)(mod 401)
∵ 10^(6015)+10^(1203)-10^(15)-10^(k) => 10^(3) - 10^(k)≡0(mod 401)

01. 합동(Congruence)

● 정의
- a,b를 m으로 나눈 나머지가 같을 때, a와 b가 m에 관하여 합동이라고 하고 a≡b(mod m)으로 나타낸다.

●modular연산
a≡b(mod m)
1. a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같다.
2. a = x*m + b (x는 임의의 정수)

● 합동의 기본 성질
- a≡b(mod m)이고, c≡d(mod m)라면 ( a=m*x1+r1, b=m*y1+r1, c=m*x2+r2, d=m*y2+r2 )
1. a+c≡b+d(mod m)
※ 증명
① a+c = (m*x1+r1) + (c=m*x2+r2) = m(x1+x2) + r1+r2
② b+d = (m*y1+r1) + (c=m*y2+r2) = m(y1+y2) + r1+r2
∵ a+c와 b+d는 모두 m의 배수이며, r1+r2의 값을 나머지로 갖는다.
2. a*c≡b*d(mod m)
※ 증명
위의 증명처럼 a,b,c,d에 각각 대응 되는 수식(ex, a=m*x1+r1 을 넣고 계산해보면 된다.)
3. a*n≡b*n(mod m)
※ 증명
① a*n = n(x*m + b)
② a*n = x*m*n + b*n
∵ a*n은 m의 배수이며, b*n의 값을 나머지로 갖는다.