목록컴퓨터 프로그램의 구조와 해석 (1)

Dharma

과학 과 공학의 차이

페르마의 작은 정리 n 이 소수고 , a 가 n 보다는 작고 0 보다는 큰 정수라면 , a^n (a 의 n 승) 은 a modulo n 으로 맞아 떨어진다. 이러한 페르마 검사가 확실하게 소수를 판별하지는 못한다. 역이 성립이 안하기 때문이다. 즉 소수가 아닌데도 페르마의 작은 정리를 만족시키는 값이 존재하기 때문이다. 이러한 수를 카마이클 수 (Carmichael number)라고 하는데, 이 수는 아주 드물다는 점 밖에 알려진 성질이 없다. 1000,000,000 아래에는 25개가 있고 예를 들자면 (561, 1105, 1729, 2465, 2821, 6601) 사실 아주 큰 값을 마구잡이로 골라 그 수가 소수인지 알아볼 때, 페르마 검사가 틀릴 확률은 우주선 (우주에서 온 방사선 cosmic rad..
프로그래밍 2012. 9. 10. 08:52
이전 Prev 1 Next 다음