---
title: Primality Tests
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# Primality Tests
如何測試一個數字 $n$ 是否為質數呢?

## Fermat Test
根據 [Fermat's Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y)
可以知道 p 若是質數則
- $a^{p-1} \equiv 1\ (mod\ p),\ a \in Z_p^*$

利用這個測試，隨機挑 $a \in Z_p^*$，檢查是否有滿足上面式子即可

但是這個測試會有 Carmichael numbers 問題

### Carmichael numbers
- [Wiki](https://en.wikipedia.org/wiki/Carmichael_number)

若符合以下情況
- $a^{n-1} \equiv 1\ (mod\ n)$, $a$ 為 $Z_n^*$ 中任一跟 $n$ 互質的數
- $n$ 是合數

則 $n$ 就稱為 Carmichael numbers

### 例子
- [Verifying Carmichael numbers](https://math.stackexchange.com/questions/22461/verifying-carmichael-numbers)

例如 $561 = 3 \times 11 \times 17$

根據 [Fermat's Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y) 可知
$a^2 \equiv 1\ (mod\ 3)$
$a^{10} \equiv 1\ (mod\ 11)$
$a^{16} \equiv 1\ (mod\ 17)$

$lcm(2, 10, 16) = 80$
$a^{80} \equiv (a^2)^{40} \equiv 1\ (mod\ 3)$
$a^{80} \equiv (a^{10})^{8} \equiv 1\ (mod\ 11)$
$a^{80} \equiv (a^{16})^{5} \equiv 1\ (mod\ 17)$

將 $a^{80}$ 替換為 $x$
$x \equiv 1\ (mod\ 3)$
$x \equiv 1\ (mod\ 11)$
$x \equiv 1\ (mod\ 17)$

根據 [中國餘式定理 CRT](https://hackmd.io/@LJP/B17an2I8t)
解為

| 軸 | $a_i$ | $M_i$ | $y_i$ |
| -- | -------- | -------- | -------- |
| $mod\ 3$ | 1 | $11 \times 17 = 187$ | 1 |
| $mod\ 11$ | 1 | $3 \times 17 = 51$ | 8 |
| $mod\ 17$ | 1 | $3 \times 11 = 33$ | 16 |

$a^{80} \equiv x \equiv 187 + 408 + 528 \equiv 1123 \equiv 1\ (mod\ 561)$

$a^{561} \equiv a\times (a^{80})^7 \equiv a\ (mod\ 561)$
$a^{560} \equiv 1\ (mod\ 561)$
如此證明出 561 就是 Carmichael numbers

## Miller-Rabin Test
參考
- [Primality Tests](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)
- [Miller-Rabin素性测试算法详解](https://blog.csdn.net/ECNU_LZJ/article/details/72675595)

進階閱讀
- [RABIN-MILLER PRIMALITY TEST: COMPOSITE NUMBERS WHICH PASS IT](https://www.jointmathematicsmeetings.org/mcom/1995-64-209/S0025-5718-1995-1260124-2/S0025-5718-1995-1260124-2.pdf)

若 $n$ 為質數，根據 [Fermat's Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y)，可取 $a \in Z_n^*$，此 $a$ 符合

$a^{n-1} \equiv 1\ (mod\ n)$

根據 [Lemma 1](https://hackmd.io/@LJP/r1kyAhLIt#Lemma-1) 可得知

$a^{(n-1)/2} \equiv \pm 1\ (mod\ n)$

若 $a^{(n-1)/2} \equiv 1\ (mod\ n)$ 則可繼續往下推得

$a^{(n-1)/2^2} \equiv \pm 1\ (mod\ n)$

Miller-Rabin Test 就是利用這個性質來檢查 $n$ 是否為質數

先將 $n-1$ 換為 $2^s \times q,\ q \perp 2$ 的形式

隨機挑一個 $a \in Z_n^*$

首先測試 $a^{2^sq} \equiv 1\ (mod\ n)$
- 這關是測試是否滿足 $a^{n-1} \equiv 1\ (mod\ n)$
- 也就是 [Fermat Test](#Fermat-Test) 做的事情 (且它也只驗證到這邊)

如果第一關就沒過，$n$ 就不是質數

過了第一關後繼續測試 $a^{2^{s-1}q} \equiv \pm 1\ (mod\ n)$
- 這關就是使用 [Lemma 1](https://hackmd.io/@LJP/r1kyAhLIt#Lemma-1) 的性質

這邊有三種 cases

1. 若 $a^{2^{s-1}q} \neq \pm 1\ (mod\ n)$
表示 $n$ 不是質數

2. 若 $a^{2^{s-1}q} \equiv -1\ (mod\ n)$
就停止驗證，回傳 $n$ 通過驗證
- 因為 -1 無法繼續使用 [Lemma 1](https://hackmd.io/@LJP/r1kyAhLIt#Lemma-1) 往下推
- 誤判就可能在此發生

3. 若 $a^{2^{s-1}q} \equiv 1\ (mod\ n)$
繼續測試 $a^{2^{s-2}q} \equiv \pm 1\ (mod\ n)$

可以看到第三種狀況像是進到迴圈，若一直測試到
$a^{q} \equiv 1\ (mod\ n)$
仍然成立，則也說 $n$ 通過驗證
- 但其實也不能保證說 $n$ 的確就是質數

只要是質數，一定能通過這個測試
但不是質數還是有機會通過測試
每次驗證錯誤率是 $1/4$
只要重複驗證(挑不同的 $a$)錯誤率就會指數性下降