유력 소수

유력 소수(probable prime) 또는 확률적 소수는 소수이기 위한 어떤 강한 필요조건을 만족하는 수를 가리킨다. 여기서 말하는 '강한 필요조건'은 모든 소수가 이 조건을 만족해야 하지만 대부분의 합성수는 그렇지 않다는 의미이다. 여기에 일부 합성수도 이러한 조건을 만족할 수가 있다. 유력 소수이지만 실제 소수가 아닌 수를 유사소수(pseudoprime)라 한다. 약자로는 PRP라 많이 쓴다.

어떤 수가 소수인지 알려면 통상 소인수분해로 직접 나누기와 같은 방법으로 확인할 수 있다. 하지만 해당 수가 구골을 넘어갈 정도면 일일이 체크할 여력이 부족해진다. 만약 이 수가 몇으로 나누어 떨어지는지는 생각하지 않고 오로지 "소수인가 아닌가"에만 관심이 있다면, 유력 소수 여부를 검사해볼 수 있다.

유력 소수이기 위한 조건은 다른 엄밀한(필요충분조건이 증명된) 소수판정법보다는 검사가 비교적 쉬워야 하며, 그렇다고 너무 많은 예외(유사소수)가 발생하지도 않아야 한다.

다시 말해 유력 소수는 "이 수가 소수인지는 인간이 밝혀낸 범위에서 아직 모르지만, 소수 후보로 올려둘 가치는 충분하다"는 의미를 내포하고 있다. 아래는 대표적인 유력 소수 확인 방법이다.

페르마 유력 소수

페르마의 소정리는 유력 소수 여부를 확인하는 대표적인 방법이다.

[math]\displaystyle{ p }[/math]가 소수이고 [math]\displaystyle{ \gcd(a,p)=1 }[/math]일 때, [math]\displaystyle{ a^{p-1} \equiv 1 \pmod p }[/math]

여기서 [math]\displaystyle{ p }[/math]는 소수 여부를 알아보고 싶은 수이고, [math]\displaystyle{ a }[/math]는 우리가 아무렇게나 정하면 된다. 보통은 [math]\displaystyle{ a=2 }[/math]와 같이 1이 아닌 작은 수를 쓴다. 물론 해당 합동식을 만족한다고 해서 반드시 [math]\displaystyle{ p }[/math]가 소수라고 할 수는 없다. 하지만 합성수들 중 상당수는 저 합동식을 만족하지 않기에, 이 정리를 이용하면 극소수의 예외를 제외하고 합성수를 거의 대부분 걸러낼 수 있다.

물론 페르마 합동식을 만족하지만 합성수인 경우도 있다. 어떤 합성수가 [math]\displaystyle{ a^{N-1} \equiv 1 \pmod N }[/math]을 만족한다면 이를 [math]\displaystyle{ a }[/math]를 밑으로 하는 페르마 유사소수(base-[math]\displaystyle{ a }[/math] Fermat's pseudoprime)라 한다.

가령 소수 [math]\displaystyle{ p }[/math]에 대해 메르센 수인 [math]\displaystyle{ M_p=2^p-1 }[/math]가 합성수이면 이 수는 2를 밑으로 하는 페르마 유사소수이다. 메르센 수의 성질에 의하면 [math]\displaystyle{ M_p-1 = rp }[/math]인 자연수 [math]\displaystyle{ r }[/math]가 존재한다. 또한 [math]\displaystyle{ 2^p \equiv 1 \pmod{M_p} }[/math]이므로 양 변에 [math]\displaystyle{ r }[/math]제곱을 하면 [math]\displaystyle{ 2^{M_p-1} \equiv 1 \pmod{M_p} }[/math]이 되어서, 페르마 합동식을 만족한다. 일례로 [math]\displaystyle{ M_{11}=2047 }[/math]은 23으로 나누어 떨어지므로 합성수이지만 [math]\displaystyle{ 2^{M_{11}-1} \equiv 1 \pmod{M_{11}} }[/math]이므로 페르마 유사소수가 된다. 물론 밑을 2 대신 다른 걸로 바꿔서 대입하면 웬만해서는 소수가 아님을 밝혀낼 수 있다.

비슷한 예로 소수 자릿수의 [math]\displaystyle{ n }[/math]진법 단위 반복 수인 [math]\displaystyle{ \frac{n^p-1}{n-1} }[/math]는 [math]\displaystyle{ n }[/math]을 밑으로 하는 페르마 유력 소수이며, 그 중 합성수는 유사소수이다.

오일러-야코비 유력 소수

이와 관련한 내용은 솔로베이-슈트라센 소수판정법에서 볼 수 있습니다.

위의 페르마의 소정리보다 좀 더 강력한 소수 조건으로 오일러의 규준이 있다. 홀수 소수 [math]\displaystyle{ p }[/math]와 서로소인 [math]\displaystyle{ a }[/math]가 주어져 있을 때, [math]\displaystyle{ \displaystyle a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \equiv \pm 1 \pmod p }[/math]를 만족한다. 여기서 [math]\displaystyle{ \displaystyle \left(\frac{a}{p}\right) }[/math]는 르장드르 기호이다.

어떤 자연수가 [math]\displaystyle{ a^{n-1} \equiv 1 \pmod n }[/math]을 만족한다고 하자. 만약 이 자연수가 소수이면 [math]\displaystyle{ a^{\frac{n-1}{2}} \equiv \pm 1 \pmod n }[/math]이 성립한다. 하지만 합성수의 경우 [math]\displaystyle{ x^2 \equiv 1 \pmod n }[/math]이면서 [math]\displaystyle{ x \not \equiv \pm 1 \pmod n }[/math]인 예외가 존재한다. 따라서 합동식에 [math]\displaystyle{ n-1 }[/math]의 절반인 [math]\displaystyle{ \displaystyle \frac{n-1}{2} }[/math]을 지수로 대입해서 나머지가 ±1인지를 알아본다면, 더 많은 예외를 걸러낼 수 있다.

오일러-야코비 유력 소수는 [math]\displaystyle{ \displaystyle a^{\frac{n-1}{2}} \equiv \left(\frac{a}{n}\right) \pmod n }[/math]을 만족하는 자연수 [math]\displaystyle{ n }[/math]을 말한다. 여기서 [math]\displaystyle{ \left(\frac{a}{n}\right) }[/math] 항은 [math]\displaystyle{ n }[/math]이 소수인지를 모르므로 르장드르 기호가 아닌 야코비 기호이다.

여기서 [math]\displaystyle{ a=2 }[/math]일 때 야코비 기호의 값은 [math]\displaystyle{ n \equiv \pm 1 \pmod 8 }[/math]일 때 +1, [math]\displaystyle{ n \equiv \pm 3 \pmod 8 }[/math]일 때 -1이다.

강한 유력 소수

이와 관련한 내용은 밀러-라빈 소수판정법에서 볼 수 있습니다.

위의 오일러-야코비 유력 소수 조건을 변형하면 아래와 같이 강한 유력 소수(strong probable prime, SPRP)를 정의할 수 있다.

어떤 홀수 자연수가 [math]\displaystyle{ n=d \cdot 2^k+1 }[/math] 꼴로 표현된다고 하자. 여기서 [math]\displaystyle{ d }[/math]는 홀수로, [math]\displaystyle{ d,k \gt 0 }[/math]의 값은 유일하게 정해진다. [math]\displaystyle{ n }[/math]과 서로소인 [math]\displaystyle{ a }[/math]에 대해 [math]\displaystyle{ a^d \equiv \pm 1 \pmod n }[/math]이거나 어느 적당한 [math]\displaystyle{ 0\lt r\lt k }[/math]가 존재하여 [math]\displaystyle{ a^{d \cdot 2^r} \equiv -1 \pmod n }[/math]을 만족하면, [math]\displaystyle{ n }[/math]은 강한 유력 소수이다.

이 조건을 달리 표현하자면, 어떤 [math]\displaystyle{ n-1 }[/math]의 짝수 약수 [math]\displaystyle{ 2b }[/math]가 [math]\displaystyle{ a^{2b} \equiv 1 \pmod n }[/math]을 만족한다면 [math]\displaystyle{ a^b \equiv \pm 1 \pmod n }[/math]이어야 하며, 그렇지 않으면 [math]\displaystyle{ n }[/math]은 강한 유력 소수가 아니다. (즉 소수가 될 수 없다)

341을 예로 들어보면 아래와 같다.

• [math]\displaystyle{ 341=85 \cdot 2^2 + 1 \rightarrow d=85,k=2 }[/math]
• [math]\displaystyle{ 2^{85} \equiv 32 \pmod{341} }[/math]
• [math]\displaystyle{ 2^{170} \equiv 1 \pmod{341} }[/math]
• [math]\displaystyle{ 2^{340} \equiv 1 \pmod{341} }[/math]

셋째 조건을 보면 341은 2를 밑으로 하는 페르마 유력 소수이다. 하지만 둘째 식에서 341은 8로 나눈 나머지가 5이므로 [math]\displaystyle{ \displaystyle \left(\frac{2}{341}\right)=-1 }[/math]이어야 하지만 합동식의 우변은 +1이므로 오일러-야코비 유력 소수가 아니며, 341은 소수 후보에서 탈락한다. 한편 첫째와 둘째 식에서 [math]\displaystyle{ 85=b }[/math]라 할 때 [math]\displaystyle{ 2^{2b} \equiv 1 \pmod{341} }[/math]이지만 [math]\displaystyle{ 2^b \not \equiv \pm 1 \pmod{341} }[/math]이므로 341은 강한 유력 소수가 아니다.

2를 밑으로 하는 강한 유력 소수 중 가장 작은 합성수는 2047이다.

유력 소수임을 알고 있다면

유력 소수 검사를 거친 결과 조건을 만족한다면 다른 조건을 가져와서 교차검증을 한다. 만약에 교차검증 단계에서 합성수임이 판명 나면 그 수는 소수 후보에서 탈락한다.

그런데 여러 가지 조건으로 검사해도 여전히 유력 소수 지위를 잃지 않는다면, 이제 이 수가 소수인가 하는 합리적 의심(?)을 할 수 있다. 물론 이러한 유추가 확정으로 굳어지려면 엄밀한 소수판정법이 필요하다. 대표적인 검증 방법으로 타원곡선 소수판정법이 있다.

외부 링크

• The prime glossary - Probable prime
• 발견된 가장 큰 유력 소수 목록: 정기적으로 목록이 갱신되며 메인 페이지에서는 최상위 250개 목록을 볼 수 있다. 합성수 혹은 확실한 소수로 판명나면 목록에서 제외된다.