페르마의 작은 정리 

n 이 소수고 , a 가 n 보다는 작고 0 보다는 큰 정수라면 ,   a^n  (a 의 n 승) 은 a modulo n 으로 맞아 떨어진다. 


 
이러한 페르마 검사가 확실하게 소수를 판별하지는 못한다. 역이 성립이 안하기 때문이다.  즉 소수가 아닌데도 페르마의 작은 정리를 만족시키는 값이 존재하기 때문이다. 이러한 수를 카마이클 수 (Carmichael number)라고 하는데, 이 수는 아주 드물다는 점 밖에 알려진 성질이 없다.  1000,000,000 아래에는 25개가 있고 예를 들자면 (561, 1105, 1729, 2465, 2821, 6601) 사실 아주 큰 값을 마구잡이로 골라 그 수가 소수인지 알아볼 때, 페르마 검사가 틀릴 확률은 우주선 (우주에서 온 방사선 cosmic radiation )이 '올바른' 알고리즘을 돌아가는 컴퓨터를 고장나게 만들어 틀린 답을 내놓게 하는 확률보다 작다. 

처음에는 틀렸기 때문에 알맞지 않은 알고리즘이라고 했다가, 나중에는 쓸 만하다고 하였는데, 바로 이런 판단 기준의 차이가 수학(과학)과 공학(기술)의 차이를 말해주는 좋은 보기다. 

                                                                          - 컴퓨터 프로그램의 구조와 해석 중에서..

완벽하게 설명이 되어야 하는 학문의 영역과 , 완벽하지는 않지만 쓸만하군 (공학) 바로 그 차이가 요즘 물질 문명의 바탕이 된 게 아닌가 싶습니다. 적어도 이러한 페르마의 작은 정리와 소수를 생성하는 그 검사로 인해서 RSA 암호화 알고리즘이 시작됐다고 하니까 말입니다. 주변에서 찾아보면 이러한 과학과 공학의 차이를 느낄 수 있는 예들이 종종 있습니다. 즉 공학은 현실과의 타협입니다. 적당한 선에서 말이죠 
 
 

+ Recent posts