정수론 | Crypt

정수론

2021/02/19 ・

$ϕ (n) = \prod p_{i}^{a_{i} - 1} (p_{i} - 1)$

오일러 피(파이) 함수 $ϕ (n)$ 는 $1$ 부터 $n$ 까지 정수 중 $n$ 과 서로소인 수의 개수를 세는 함수이다.

2021/02/11 ・

$(\binom{m}{n}) \equiv \prod_{i = 0}^{k} (\binom{m_{i}}{n_{i}}) (\mod p)$

뤼카의 정리는 음이 아닌 정수 $m, n$ 소수 $p$ 에 대해 $(\binom{m}{n}) mod p$ 를 쉽게 구할 수 있게 해주는 정리다.