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

베르트랑의 공준 증명에서 조그만한 아이디어를 가져왔다.

소수 밀도 하한에 대한 초등적이면서 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)$라고 하자.

$$ \begin{align} f_N (p) &= \sum_{i=1}^\infty \left( \left\lfloor \frac{2n}{p^i} \right\rfloor - 2 \left\lfloor \frac{n}{p^i} \right\rfloor \right) \\ &\leq \sum_{i=1}^{\lfloor \log_p 2n \rfloor} 1 \leq \log_p 2n \end{align} $$

$N = \binom{2n}{n}$의 모든 소인수는 $2n$ 이하이다.

$$ \begin{align} N &= \prod_{p \leq 2n} p^{f_N (p)} \\ &\leq \prod_{p \leq 2n} 2n \\ &= (2n)^{\pi(2n)} \end{align} $$

그러므로 $2^n \leq N \leq (2n)^{\pi(2n)}$에 의해 본 claim이 성립한다.

 

또한 $n \geq 2$에 대해 $\pi(2n-1) = \pi(2n)$ 이므로 본 theorem이 성립한다.

 

 

.

 

암호학에서 uniformly random하게 발생시킨 임의의 $n$비트 정수는 적어도 $1/2n$ 이상 확률로 소수이다.

생각보다 조금만 찾아도 RSA에 쓰일 비밀키를 만들 수 있다.