etc
페르마의 소정리
_its
2019. 6. 20. 20:50
p가 소수이고, a가 p로 나누어지지 않는 정수(서로소)이면
\[a^{p-1}\equiv1(\bmod p)\]
\[a^{p}\equiv a(\bmod p)\]
p가 소수이면 페르마의 소정리를 만족하지만, 역은 성립하지 않음.
p가 합성수이면서 정리를 만족하는 경우, 이런 p를 유사소수라 함.
(합동 : 나머지가 같은 두 정수 사이의 관계)
(합성수 : 1보다 큰 모든 정수 중 소수가 아닌 수)
RSA방식으로 암복호화하는 과정에 활용.