ㅅㅂ 재밌긴한데 뭔 소린지 모르겠네;;
어쨌든 무엇이냐면 prime인지 여부를 조사하는 한 방법인데 페르마의 소 이론이라고 a라는 prime과 그보다 작은 prime p간에는
a ^ (p-1) = 1 mod p 이딴 관계가 있다는 것임.
그런데 이게 그 역은 성립하지 않아서 모종의 함정을 통해 Composite 수를 잡을 수 있는데 그게 Miller-Rabin Test라고 함.
간단하게 말하면 어차피 prime은 2를 제외하고 모두 홀수라는 점을 이용한건데 따라서 p가 짝수인 경우는 다 걸러재끼고,
p가 홀수인 경우에만 p-1을 2^e * 어떤 N 의 모양새로 바꿔버리는거임 (물론 ㅄ이 아닌 이상 e도 자연수인건 알거임)
그러면 a ^ (p-1) = 1 mod p이므로 a ^ (p-1) - 1 = 0 mod p가 되는데 이를 이용하는 것이다.
.... 질문하지마라.
