이 글의 내용은 성균관대학교 권순학 교수님의 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}\)로 매우 작으므로 실제로 사용 가능한 소수판정법이다.