정수론 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 \) {#lemma-6-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}\)로 매우 작으므로 실제로 사용 가능한 소수판정법이다.