in_the_silences
페르마의 소정리 본문
p가 소수이고, a가 p로 나누어지지 않는 정수(서로소)이면
\[a^{p-1}\equiv1(\bmod p)\]
\[a^{p}\equiv a(\bmod p)\]
p가 소수이면 페르마의 소정리를 만족하지만, 역은 성립하지 않음.
p가 합성수이면서 정리를 만족하는 경우, 이런 p를 유사소수라 함.
(합동 : 나머지가 같은 두 정수 사이의 관계)
(합성수 : 1보다 큰 모든 정수 중 소수가 아닌 수)
RSA방식으로 암복호화하는 과정에 활용.
'etc' 카테고리의 다른 글
| 오일러 피 함수 (0) | 2019.06.27 |
|---|---|
| Design Patterns (0) | 2017.10.25 |
| C++ string (0) | 2017.09.17 |
| Tensor Flow & Unit Test & cin팁 & /n의 속도 (0) | 2017.09.04 |
| git 협업 준비 규칙 (0) | 2017.08.01 |
Comments