소수 판별법(페르마 테스트)

🌟 소수는 1과 자신 이외는 약수로 가지지 않는 1보다 큰 자연수이다.

 

🟩 페르마 테스트 = 확률적 소수 판별법

어떤 수가 '소수일 가능성이 높은지'를 판별하는 것

 

1. 해당 수보다 작은 수를 해당 수만큼 제곱한다. 예)5 -> 1^5 ~ 4^5

2. 각각의 숫자를 mod 연산을 이용해 해당 수로 나눈다. 예) 1^5 = 1 mod 5 = 1

3. 원래 수와 나머지 값이 모두 일치하면, 소수이다.

 

페르마의 소정리를 만족하는지를 소수 판별을 하는 방법이 '페르마 테스트'

 

일치하는지 확인하는 횟수를 늘릴수록 소수일 확실성이 높아진다. 단 p보다 작은 모든 수를 확인하려면 매우 오랜 시간이 걸린다. 실제로는 몇 개의 수만 확인해서 소수일 가능성이 매우 높다고 판단할 수 있으면 '아마도 소수'라고 판정하고 있다. 

 

cf. 작은 수 n이 식을 만족하는 합성수(소수가 아닌 자연수)일 경우, 소수라 할 수 없다. 예를 들어 561 = 3 * 11 * 17로 나타낼 수 있으므로, 소수가 아니다. 하지만 561보다 작은 수들은 모두 식을 만족한다. 이런 합성수를 '카마이클 수 or 절대 유사소수'라 한다. 

 

카마이클 소수 예 (많지 않음)

561 1105 1729 2465 2821 6601 8911 10585 15841 29341 41041 46657 52633 62745 63973