페르마의 소정리

* 페르마의 소정리

  다른 이론의 근간 또는 여러 암호학 수학의 기반이 되는 매우 중요한 이론이라 함 알아봤는데, little theorem이라곤 하는데 다방면에 쓰이는 걸 보니 작은 정리이긴한데 매우 큰(?) 개념임을 알 수 있었습니다.. 단 이 포스팅에선 증명을 포함하지 않았습니다. 오일러 정리라던지 다른 개념을 알아야 하기에 나중에 포스팅할 숙제로 남겨놓겠습니다..

  페르마 소정리의 기본 명제는 다음과 같습니다.

p가 소수이다. ^ a와 p는 서로소이다. -> 

여기서 파생되는 명제 중 하나는 아래와 같습니다.

  

  즉 a의 곰셈 역원는 이다.

  이 명제는 modularity에서 수에 대한 매우 큰 승수를 구할 때 사용할 수 있습니다.

보조 정리 1) p와 서로소인 모든 a에 대해 인 1<=b<=p에 반드시 하나 존재한다.

증명) a의 곱셈 역원 b는 이며 이는 변수가 아닌 정해진 상수입니다. 따라서 반드시 하나 존재할 수 밖에 없습니다.

보조 정리 2) 자가 상쇄 원소(self-canceling elements)는 1과 p-1이다.

증명) 자가 상쇄 원소라 함은 곱셈 역원이 곧 자기자신임을 말합니다. 1 * 1 = 1 이므로 자명하고, p-1의 경우 수식으로 증명이 가능합니다.

  

보조 정리 3) 보조 정리1, 2를 기반으로 윌리엄스 증명에 의하면  이다.

증명) 자가 상쇄원소 1과 p-1을 제외한 모든 요소는 반드시 역원이 1과 p 사이에 존재하며 그 둘을 곱하면 1이 되므로 1과 p-1만이 남습니다. 당연히 1과 p-1의 곱셈은 p-1이므로 위 수식이 맞음을 알 수 있습니다.

* 소수 판별법의 페르마 소정리

  p가 소수임을 판별하기 위해 페르마 소정리를 사용할 순 없습니다. 즉 페르마 소정리의 역(converse)인 아래 명제는 거짓입니다.

   -> p가 소수이다.

  p가 합성수이면서 페르마 소정리를 만족하는 수를 카마이클 수(Carmichael number)라고 합니다. 이 카마이클 수가 무한히 많음을 증명이 되어있습니다. 따라서 페르마 소정리로 소수 판별하는 것은 확실하지 않은 확률화 알고리즘으로 분류가 되어있습니다.

    * 카마이클 수(Carmichael number)

    카마이클 수는 유사 소수(psuedo prime)라고도 합니다.

    이 수 집합의 부분 집합을 아래 수식으로 쉽게 구할 수 있습니다.

      

    J. Chernick이 가능함을 증명했습니다.

    참고로 2016 중국인이 다른 구할 방법을 찾았다곤 합니다. 궁금하시면 아래를 클릭. 전 몰라도 될 거 같아서..ㅎ

    (https://edition.cnn.com/2016/07/17/asia/china-migrant-worker-good-will-hunting/index.html)

* 첨언

   프로그래밍에서 경우의 수 또는 수 자체가 커지면 Modularity를 사용합니다. 페르마의 소정리에 의해 합동을 증명했기 때문에 적당히 큰 소수 10^9 + 7 또는 10^9 + 9를 자주 사용하는 것을 볼 수 있습니다. 수학이나 프로그래밍에 자주 사용하기 때문에 반드시 제대로 알고 넘어가는 것이 좋을 것 같아요.

* 페르마 소정리 개념만이 들어간 프로그래밍 문제

https://www.acmicpc.net/problem/4357

  - 희한한 알고리즘을 요구하는 문제. 아직 풀어보진 못함.

https://www.acmicpc.net/problem/13319

  - 이 문제의 경우 카마이클 수를 구하면 됩니다. 단, [1, 500]에서 x^(p-1)이 1이어야 하므로 반드시 500 < 6k+1을 만족하는 수를 찾아야 합니다.

https://www.acmicpc.net/problem/4233