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