공부 저장소

Mathematics 검색 결과

해당 글 6건

스포츠 경기 레이팅 (ELO) 시스템, 사람들의 실력을 어떻게 수학적으로 정의할 것인가?

회사에서 배드민턴 동아리 활동을 했다. 인기가 많은 동아리라 참여 인원이 많았고, 이에 자동 매칭 시스템을 만들어봐야겠다는 동기가 생겼다. 필연적으로 다음 과제를 해결해야한다: 사람들의 실력을 어떤 방식으로 정량화를 할 수 있을까? 그 고민의 결과가 나름 재미있어서 블로그에 옮겨보았다. 잘 정립된 기존 방식 중 하나는 FargoRate라는 것이 있다. 상대 전적에 따라 점수가 결정되며, 초보자는 100점, 월드 클래스 선수는 800점대로 분포가 된다. 가장 중요한 특징은 두 플레이어가 맞붙었을 때 승패 확률이 레이팅에 의해 결정된다는 점이다. 300점대의 두 플레이어가 붙었을 때 이길 확률은 서로 동일하며, 300점대 플레이어와 400점대 플레이어가 붙어서 나올 승패의 확률도 어느 정도 결정되어있다. 하..

Mathematics 4개월 전

삼각함수의 특수각은 왜 몇 개 없는가?

중학교 교육과정에서 처음 삼각함수를 배울 때 드는 의문점이 있다. 왜 삼각함수의 특수각은 0, 30, 45, 60, 90도 밖에 안 알려주는 것일까? 정말로 다른 각도들에 대해서는 너무 어려운 삼각비가 나오거나, 혹은 간단한 삼각비가 나오는 각도들은 모두 복잡한 것일까? 각도와 삼각비가 동시에 간단한 경우는 우리가 학창시절에 배웠던 것처럼 몇 안 되는 것 인지, 본 게시물에서 밝혀보겠다. 1. 삼각함수 특수각의 정의 나는 삼각함수의 특수각을 아래와 같이 정의하였다. 정의 1.1 (특수각) 정수 $n, m, p, q$에 대해 아래를 만족하는 각도 $\frac{m \pi}{n}$를 특수각으로 정의한다. $$\sin^2 \left( \frac{m \pi}{n} \right) = \frac{q}{p}$$ 즉..

Mathematics 2년 전

생일 패러독스, 생일 공격

$n$명의 사람이 있다. 이 사람들의 생일이 모두 다를 확률은 얼마나 될까? $$\prod_{i=1}^{n-1} \left( 1 - \frac{i}{365} \right)$$ 이다. 이 경우 $n = 23$만 되어도 이미 확률이 절반 이하가 된다. 생각보다 적은 수의 사람이 모여도 꽤 높은 확률로 생일이 같은 두 사람을 찾을 수 있다는 것이 생일 패러독스이다. 이를 이용하여 충돌쌍 하나를 효과적으로 구하는 암호론적 공격이 생일 공격이다. 해시함수의 충돌값을 찾거나, 블록암호를 공격할 때 사용된다. Factoring 문제를 효과적으로 푸는 Pollard's rho 랜덤 알고리즘도 똑같은 원리를 기반으로 한다. 특히 블록암호에서 어떤 함수 $G$에 대해 $G(x) = G(y)$인 서로 다른 문자열 $x,..

Mathematics 5년 전

소수 밀도 하한의 간단한 증명

베르트랑의 공준 증명에서 조그만한 아이디어를 가져왔다. 소수 밀도 하한에 대한 초등적이면서 Big-$O$ 표기법으로는 실제와 동일한 결과가 나오는 간단한 증명인 것 같다. 1부터 $n$까지 소수의 개수를 $\pi(n)$이라고 하자. Theorem. 임의의 자연수 $n$에 대하여 $$\pi(n) \geq \frac{n}{2 \log n}$$ 이다. (단 이 글에서 모든 생략된 로그 밑은 2이다.) Claim. $$\pi(2n) \geq \frac{2n}{2 \log 2n}$$ (Proof) $\binom{2n}{n} = N$이라고 하자. 수학적 귀납법에 의해 $N \geq 2^n$을 만족한다. 소수 $p$에 대하여, $p^e | N$이 성립하는 $e$의 최대값을 $f_N(p)$라고 하자. $$ \b..

Mathematics 5년 전

Even-Mansour 블록 암호 security는 2^(n/2) 증명

Even-Mansour 블록 암호란 $n$비트 스트링을 $n$비트 스트링으로 암호화하는 대칭키 암호 시스템이다. 어떤 퍼뮤테이션 $F : \{0, 1\}^n \rightarrow \{0, 1\}^n$이 고정되어 있고(이는 공개적으로 알려져 있다.), 키는 $n$비트 스트링 $K_1, K_2 \in \{0, 1\}^n$이다. 암호화 방식은 $M \in \{0, 1\}^n$ 평문을 받아서 $C = E_{K_1, K_2} (M) = K_2 \oplus F(K_1 \oplus M)$ 으로 구현한다. $F$ 퍼뮤테이션의 역도 계산 가능하므로 복호화는 $M = K_1 \oplus F^{-1} (K_2 \oplus C)$ 로 쉽게 처리할 수 있다. 암호론 교수님께서 본 암호의 security가 $2^{n/2}$ 임을..

Mathematics 5년 전

행렬 AB와 BA의 고유값(eigenvalue)은 서로 같은가?

두 행렬의 크기가 서로 달라 고유값의 개수가 다를 수도 있지만, 놀랍게도 추가적인 고유값들은 모두 0이다. 즉 $AB$의 고유값을 $x_1, x_2, \dots x_n$, $BA$의 고유값을 $y_1, y_2 \dots, y_m$ ($n \leq m$이라 가정) 으로 두면, $x_1 = y_1, x_2 = y_2, \dots, x_n = y_n$, $y_{n+1} = y_{n+2} = \cdots = y_m = 0$ 을 만족하는 재배열이 존재한다는 것이다. 보조정리 1. $A$가 $m \times n$, $B$가 $n \times m$ 행렬이라고 하자. 그렇다면 아래를 만족한다. $$tr(AB) = tr(BA)$$ (증명 생략) 보조정리 2. $$tr ((AB)^k) = tr ((BA)^k)$$ ..

Mathematics 5년 전