페르마 소정리

페르마의 소정리

RSA 암호를 이해하기 위해서는 수학에 대한 일정 수준의 이해가 요구된다. 암호와 관련된 배경 지식으로 ‘페르마의 소정리’와 ‘오일러의 정리’를 알아보자. 17세기 프랑스의 수학자 피에르 페르마(Pierre de Fermat, 1601~1665)는 그의 이름이 붙은 수많은 정리를 남겼는데, 그중 ‘페르마의 소정리’는 다음과 같다.

 

p가 소수이고 a와 p가 서로소이면 ap-1≡1(mod p)이다.
즉, ap-1을 p로 나누면 나머지가 1이다.

이 정리를 확인하기 위해 p=7, a=2로 놓자. 27-1≡26≡1(mod 7), 즉 26=64를 7로 나누면 몫이 9이고 나머지가 1이므로, 위의 정리가 성립함을 알 수 있다.

 

페르마의 소정리를 일반화한 것이 18세기 스위스의 수학자 오일러가 증명한 ‘오일러의 정리’이다.

자연수 n에 대해 a와 n이 서로소이면, 즉 a와 n의 최대공약수가 1이면 aф(n)≡1(mod n)이다. (ф(n)은 1부터 n까지의 수 중 n과 서로소인 자연수의 개수를 말한다.)

오일러의 정리에서 n을 소수 p로 놓으면 바로 페르마의 소정리가 된다. 소수 p는 1부터 p-1까지의 모든 자연수와 서로소이기 때문에 ф(p)=p-1이 되기 때문이다. 이제 RSA 암호를 이해할 수 있는 사전 지식을 갖추었으므로 내용 설명으로 들어가자.

[네이버 지식백과] 페르마의 소정리 (박경미의 수학콘서트 플러스, 2013. 12. 12., 박경미)