고상한 여인네가 천한 일을 마다하지 않는 것을 보는 순간, 그렇게 아름답게 보일 수가 없다. 더이상 그녀가 아프지 않고 살아가기를 빌게 된다. 우리 사회에는 상당수가 어쩔 수 없는 직업을 갖는 경우가 많다. 공부를 못해서 할 수밖에 없는 일들부터, 돈에 궁핍하다 보니 어쩔 수 없이 하는 일들, 이래도 죽지 못해 사는 사람들이 없다고는 하지 말라. 필자도 진짜 죽을 수는 없으니, 파산을 피하기 위해 발버둥을 치고 있다. 난 에 평화가 싫어지고 있는 것이다.
지금까지 소수 판별법은 소인수 분해를 해보는 것 이상 특별한 게 없다. 수많은 소수 판별법은 한계를 갖고 있으며, 보다 나은 소수 판별법은 앞으로 지속적으로 연구할 가치가 있는 것이다.
소수 판별법 중에 가장 손쉬운 방법중 하나인 페르마 소수 판별법이 오류가 있지 않나 적어본다. 그리고 이 오류는 우리가 메르센 소수에서 일반적인 진리로 여겨온 소수 판별 과정에서도 오류가 된다는 것을 연관지어 생각해보기를 바란다.
페르마 소수 판별법은 밑수 A와 지수P-1에서 P가 소수일때, 이 수를 P로 나누면 나머지가 1이 되는 수를 말한다. 이떄 a와 p는 서로소이고 a가 P보다 작다.
즉 a를 2로 고정시켜놓고, 소수 P인 수를 대입해보면, 이 정리가 참인지 확인할 수 있다.
그리고 A를 2라고 하면, 메르센 소수 판별 법이 되기도 한다는 것을 모두 알 수 있다.
그러면 메르센 소수판별법에서 P가 소수이면, A의 P제곱-1에서 1을 뺸 수의 P가 소인수가 되어야 한다는 정리와 같은 식이 되는 것이다.
왜냐 하면, A의 P제곱-1에 -1을 2로 나누어주면, 2*(A의 P-1제곱-1)로 쓸 수 있고, 이값은 P로 나눴을때 P가 소수이면 괄호속의 수의 소인수가 되는 것이란 것과 같은 것이다.
그런데 이것이 오류가 있는 듯하다.
P를 소수일 것같지만 합성수인 2047을 대입해서 풀어보면 알 수 있다. 2의 2046제곱이 2047로 나누면 나머지가 1인 수가 되기 때문인 것이다.
나머지가 1인 수는 2의 2046제곱-1이 2047로 나누어 떨어지는 수이고, 지수 2046은 11로 나누어 떨어지니 2의 2046제곱 -1은 2의 11제곱 -1로 인수분해가 된다는 것이다.
2047은 다 알겠지만 2의 11제곱-1인 수이다. 즉 2047로 나누어 떨어지는 것이다. 2047은 소수가 아니다.
보다나은 소수판별법을 연구해야 한다. 그래서 순환마디길이를 활용한 소수판별법을 다음에 쓸 것이다.
이에 대해 챗GPT는 좋은 관점에서 페르마 소수 판별법의 문제점을 짚어주셨네요. 요약하자면, 페르마 소수 판별법은 모든 소수를 판별하는 완벽한 방법이 아니라, 특정한 합성수(카마이클 수)에서 오류를 범할 수 있다는 것이죠.
2047 = 23 × 89는 합성수이지만, 페르마 소수 판별법을 만족하기 때문에 페르마 테스트를 통과하는 "위조 소수(pseudoprime)"라는 것입니다. 이는 페르마 테스트의 약점이기도 합니다.
그리고 메르센 소수 판별법(Lucas-Lehmer Test)과 연결 지어 생각하신 것도 흥미롭습니다. 메르센 소수 판별법은 페르마 테스트보다 훨씬 정밀하지만, 일반적인 소수 판별법으로 확장하기에는 제약이 있죠.
순환마디길이를 활용한 소수 판별법에 대해 더 설명해 주시면 좋을 것 같아요! 새로운 방법이라면 기대가 됩니다.
