정수론 Chapter 6.2 - Pseudoprimes
이 글의 내용은 성균관대학교 권순학 교수님의 2019년 4월 11, 16일 수업 내용을 재구성한 것입니다.
Pseudoprimes
합성수지만 소수처럼 보이는 수를 의미한다.
Fermat pseudoprimes
Fermat’s Little Theorem을 이용하면 어떤 수가 합성수임을 밝힐 수 있다. 그런데 Fermat Little Theorem을 이용해서 테스트한 결과 소수일 때와 비슷한 결과과 나오는 합성수들이 존재한다.
합성수 \( n \)에 대해 \( a^{n-1} \equiv 1 ; (\textrm{mod}\ n)\)인 경우 \(n\)을 Fermat pseudoprime to base a 라고 한다.
예시: \( 91 \)
\( 3^{90} \equiv 1 ; (\textrm{mod}\ 91) \)이므로 \(91\)은 Fermat pseudoprime to base 3이지만, \( 2^{90} \equiv 64 ; (\textrm{mod}\ 91) \)이므로 Fermat pseudoprime to base 2가 아니다.
Lemma 6.1: \(d \mid n \Rightarrow 2^d -1 \mid 2^n - 1 \)
증명
\(d \mid n \Rightarrow \exists ; t ;; s.t. ;; dt = n\)
\( 2^n - 1 = (2^d - 1)(2^{d(t-1)} + 2^{d(t-2)} + \dots + 2^d + 1) \)
\( \therefore ; 2^d - 1 \mid 2^n - 1\)
Theorem 6.6: base 2인 fermat pseudoprime은 무한히 많다
증명
341은 fermat pseudoprime to base 2이다.
\(n\)이 fermat pseudoprime이면, \(m = 2^n - 1\)도 fermat pseudoprime이다
$$ n: odd ; fermat ; pseudoprime \\ \Rightarrow 2^{n-1} \equiv 1 ; (\textrm{mod}\ n) $$
\(n\)이 합성수이므로, \( n = dt (1 \lt d,; t \lt n) \)
증명: 합성수
Lemma 6.1에 의해 \( 2^d - 1 \mid 2^n - 1 = m\)이므로 \(m\)은 합성수이다.
증명: \(2^m \equiv 1 (\textrm{mod}\ m)\)
$$ 2^n \equiv 2 ; (\textrm{mod}\ n) \\ \Rightarrow \exists ; k ;; s.t. ;; 2^n - 2 = kn \\ \Rightarrow 2^m - 1 = 2^{2^n - 2} = 2^{kn} $$
Lemma 6.1에 의해 \(m = 2^n - 1 \mid 2^{kn} - 1 = 2^{m-1} - 1 \)
\( \therefore ; 2^{m-1} \equiv 1 ; (\textrm{mod}\ m) \)
Remark: 모든 자연수 \(a\)에 대해 base \(a\)인 fermat pseudoprime은 무한히 많다
증명은 생략한다. 증명의 아이디어는 base가 2일 때와 같다.
Concept: square free
어떤 정수 \(n\)을 소인수분해 했을 때, 모든 prime의 factor가 0 또는 1인 경우 이를 square free라고 부른다. 예를 들어서 \(3, 15, 30\)은 square-free지만, \(4, 8, 16\)은 square free가 아니다.
Carmichael Numbers
\(\gcd(b, n) = 1\)인 모든 자연수 base b에 대해 Fermat primality test를 통과하는 합성수들이 있다. 이런 수들을 Carmichael Numbers라고 부른다.
Remark: 561은 가장 작은 Carmichael Number이다
$$ n = 561 = 3 \times 11 \times 17 \\ \gcd(b, 561) = 1 \Leftrightarrow \gcd(b, 3) = 1, ;; \gcd(b, 11) = 1, ;; \gcd(b, 17) = 1 $$
$$ n - 1 = 560 = 2^4 \times 5 \times 7 $$
$$ b^{n-1} \equiv (b^{2})^{280} \equiv 1 (\textrm{mod} ; 3) \\ b^{n-1} \equiv (b^{10})^{56} \equiv 1 (\textrm{mod} ; 11) \\ b^{n-1} \equiv (b^{16})^{35} \equiv 1 (\textrm{mod} ; 17) $$
Carmichael Number은 무한히 많다
증명은 생략한다.
정리의 의미
이 정리는 모든 base에 대해 Fermat’s Primarillity Test를 통과하는 합성수가 무수히 많다는 걸 의미하고, 이는 Fermat’s Primarillity Test를 소수를 판별하는 데 쓸 수 없다는 것을 뜻한다.
Theorem 6.7: square free인 \(n\)이 모든 \(j\)에 대해 \(p_j -1 \mid n - 1\)을 만족하면 Carmichael Number이다
\(n\): square free이고 홀수인 합성수, let \(b\): 자연수 \(s.t. ; \gcd(n, b) = 1\)
$$ n = p_1 \times p_2 \times \cdots \times p_k $$
$$ \forall j, ; 1 \le j \le k, ;; n - 1 = (p_j - 1) t_j ;; (\because p_j - 1 \mid n - 1) $$
$$ b^{n-1} = (b^{p_j - 1})^{t_j} \equiv 1 ; (\textrm{mod} ; p_j) ;; (\because Fermat’s ; Little ;Theorem) $$
$$ \Rightarrow \forall j, ; p_j \mid b^{n-1} - 1 $$
$$ \Rightarrow \prod_j {p_j} \mid b^{n-1} - 1 $$
$$ \Rightarrow n \mid b^{n-1} - 1 $$
$$ \Rightarrow b^{n-1} \equiv 1 ; (\textrm{mod} ; n) $$
따라서 \(n\)은 Carmichael Number이다.
Remark: 역도 성립한다
즉, 어떤 수 n이 Carmichael Number라는 것은 n이 square free이고 \(\forall ; q \mid n \)에 대해 \( q - 1 \mid n -1 \)이라는 것과 동치이다.
증명은 생략한다.
Strong Psedoprime
\(2\)보다 큰 양의 자연수 \(n\), 음이 아닌 정수 \(s\), 홀수 \(t\), \(\gcd(b, n) = 1\)인 \(b\)에 대해
$$ n - 1 = 2^s \times t $$
$$ b^{n-1} - 1 = b^{2^s t} - 1 = (b^{t})^{2^s} - 1 = (b^t - 1)(b^t + 1)(b^{t^2} + 1)\cdots(b^{t^{s-1}} + 1) $$
이때, \(n \mid b^{n-1} - 1\)이면, 다시 말해서, 우변에 있는 factor 중 하나라도 나누면 n을 Strong pseudoprime to base b이라 칭한다.
Remark: Strong pseudoprime이면 Fermat’s pseudoprime이다
Strong pseudoprime인 \(n\)과 \(\gcd(n, b) = 1\)인 \(b\)에 대해,
$$ b^t \equiv 1 ; (\textrm{mod} ; n) \\ or \\ \exists ; j ;; s.t. ;; b^{2^j}t + 1 \equiv 0 ; (\textrm{mod} ; n) $$
$$ \Rightarrow b^{n-1} \equiv 1 (\textrm{mod} ; n) $$
이므로 \(n\)은 Fermat pseudoprime이다.
Remark: Fermat’s pseudoprime이어도 Strong pseudoprime이 아닐 수 있다.
$$ n = 91 = 7 \times 13, ; b =3 $$
$$ n - 1 = 2^1 \times 45 $$
$$ b^{n-1} - 1 = (b^t + 1) (b^t - 1) = 28 \cdot 26 $$
$$ 26 \not \equiv 0 ; (\textrm{mod} ; n), 28 \not \equiv 0 ; (\textrm{mod} ; n) $$
따라서 n은 Strong pseudoprime to base 3이 아니다.
그런데
$$ b^{n - 1} \equiv 1 ; (\textrm{mod} ; n) $$
이므로 91은 Fermat pseudoprime to base 3이다.
Theorem 6.9: base \(2\)인 strong pseudoprime은 무수히 많다
Remark: \(b > 1\)인 임의의 b에 대해, base b인 Strong pseudoprime은 무수히 많다
증명은 어렵다고 한다.
Theorem 6.10: \(B = \{1 \le b \le n - 1 | n ; is ; strong ; pseudoprime ; to ; base ; b \}, |B| \le \frac {n - 1} {4}\)
증명은 생략한다.
Theorem 6.11: Miller-Robin Probabilistic Primality Test
홀수 \(t\)에 대해
$$ n - 1 = 2^s t $$
Step 1: \(1 \le b \le n - 1 \)인 자연수 \(b\)를 하나 선택한다
Step 2: \(b^{t} \equiv \pm 1 ; (\textrm{mod} ; n)\)이면 n은 probabilistic prime이고, 진행을 멈춘다.
Step 3: \( j = 1 ; \textrm{to} ; s - 1, ; {b^{2^jt}} \equiv -1 ; (\textrm{mod} ; n) \)이면 n은 probabilistic prime이고, 진행을 멈춘다.
Step 4: \(n\)은 합성수이다.
한 번의 시행에서 n이 probabilistic prime이라는 결과가 나왔을 때, 합성수 \(n\)이 Strong pseudoprime to base b일 확률은
$$ \frac {| B |} {n} \le \frac {1} {4} ;; (\because \textrm{Thm 6.9}) $$
(\(n\)이 소수일 경우 의미가 없는 공식)
Probabilistic Test긴 하지만, n개의 base에 대해서 probabilistic prime로 판정된 수가 소수가 아닐 확률이 \(\frac {1} {4^n}\)로 매우 작으므로 실제로 사용 가능한 소수판정법이다.