析素
擇行算:素測、分解、分析。算驗結而合素定理。
用
- 判某整為素或合→用
- 求整全素分→用
- 限內計或列素→用
- 驗某範素定理近→用
- 數論證或算察素性→用
入
- 必:析之整或分析之限
- 必:類——素測、分解、分析
- 可:偏算(試除、Miller-Rabin、Eratosthenes 篩、Pollard rho)
- 可:出形證或唯算判
- 可:出式(因樹、素列、計、表)
行
一:定類
請分為三類擇算路。
- 素測:給整 n,判 n 為素否
- 分解:給合 n,求其全素分
- 分析:給限 N,析 N 內素(計、列、隙、密)
錄類與入值。
得:明分附入值錄。
敗:入含糊(如「析 60」)→請用者明素測、分解、分析。合默為分解,疑素默為素確。
二:施素測(若類=素測)
按 n 大配算測 n 為素否。
平案:n < 2 非素。n = 2 或 3 為素。n 偶且 > 2 為合。
小 n(n < 10^6):用試除。
- 試除諸素 p 至 floor(sqrt(n))
- 優:試 2、後奇 3、5、7…或用 6k +/- 1 輪
- 無除則 n 素
大 n(n >= 10^6):用 Miller-Rabin 概測。
- 書 n - 1 = 2^s * d,d 奇
- 各證 a 於 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}:
- 算 x = a^d mod n
- x = 1 或 x = n - 1→此證過
- 否方 x 至 s - 1 次。x 嘗等 n - 1→過
- 無過→n 合(a 為證)
- n < 3.317 * 10^24 之 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 證為定
錄判:素或合,附證或證書。
首二十五素:
| Index |
Prime |
Index |
Prime |
Index |
Prime |
| 1 |
2 |
10 |
29 |
19 |
67 |
| 2 |
3 |
11 |
31 |
20 |
71 |
| 3 |
5 |
12 |
37 |
21 |
73 |
| 4 |
7 |
13 |
41 |
22 |
79 |
| 5 |
11 |
14 |
43 |
23 |
83 |
| 6 |
13 |
15 |
47 |
24 |
89 |
| 7 |
17 |
16 |
53 |
25 |
97 |
| 8 |
19 |
17 |
59 |
|
|
| 9 |
23 |
18 |
61 |
|
|
得:定答(素或合)附用算與所見證或除。
敗:Miller-Rabin 報「概素」而需確→升至定測(如 AKS 或 ECPP)。試除算太慢→換 Miller-Rabin。
三:施分解(若類=分解)
全分 n 為其素冪分。
以試除取小因:
- 除 2 盡,錄冪
- 除奇素 3、5、7、11…至截(如 10^4 或小 n 之 sqrt(n))
- 各除後更 n 為剩餘因
若餘 > 1 且 < 10^12:續試除至 sqrt(餘)。
若餘 > 1 且 >= 10^12:施 Pollard rho。
- 擇 f(x) = x^2 + c (mod n) 隨 c
- 用 Floyd 環察:x = f(x)、y = f(f(y))
- 各步算 d = gcd(|x - y|, n)
- 1 < d < n→d 為非平因。遞於 d 與 n/d
- d = n→以異 c 重試
驗:乘諸素因(附冪)確同原 n。各因素測。
以標式呈:n = p1^a1 * p2^a2 * ... * pk^ak,p1 < p2 < ... < pk。
算複雜:
| Algorithm |
Complexity |
Best for |
| Trial division |
O(sqrt(n)) |
n < 10^12 |
| Pollard's rho |
O(n^{1/4}) expected |
n up to ~10^18 |
| Quadratic sieve |
L(n)^{1+o(1)} |
n up to ~10^50 |
| GNFS |
L(n)^{(64/9)^{1/3}+o(1)} |
n > 10^50 |
得:標式之全素分,乘驗。
敗:Pollard rho 多迭不得因(環察無非平 gcd)→試異 c(至少 5 次)。皆敗→餘或為素,以素測確。
四:施分析(若類=分析)
析 N 內素分。
以 Eratosthenes 篩生素:
- 建大 N + 1 之布陣,初為真
- 設 0 與 1 為偽(非素)
- 各 p 自 2 至 floor(sqrt(N)):
- p 仍真→標諸倍 p^2、p^2 + p、p^2 + 2p…為偽
- 收諸仍真之指
計素:算 pi(N) = N 內素數。
比於素定理:
- PNT 近:pi(N) ~ N / ln(N)
- 對數積近:Li(N) = integral from 2 to N of 1/ln(t) dt
- 算相對誤:|pi(N) - N/ln(N)| / pi(N)
析素隙(可):
- 算連素隙
- 報最大隙、均隙、雙生素(隙=2)
- N 近均隙約 ln(N)
以表呈:
Bound N: 1,000,000
pi(N): 78,498
N/ln(N): 72,382
Li(N): 78,628
Relative error (N/ln(N)): 7.79%
Relative error (Li(N)): 0.17%
Max prime gap: 148 (between 492113 and 492227)
Twin primes: 8,169 pairs
得:素計附 PNT 比與可選隙析。
敗:N 太大不能內存篩(N > 10^9)→用段篩按段處範。唯需計(非列)→用 Meissel-Lehmer 直算 pi(N)。
五:算驗
以獨法交核諸結。
素測:試除用→以快 Miller-Rabin 驗(或反之)。知素查表或 OEIS 序。
分解:乘諸因確同原入。獨測諸宣素因素性。
分析:抽 3-5 篩出之數獨素測。比 pi(N) 於標基出版值(pi(10^k) k = 1, ..., 9)。
pi(N) 出版值:
| N |
pi(N) |
| 10 |
4 |
| 100 |
25 |
| 1,000 |
168 |
| 10,000 |
1,229 |
| 100,000 |
9,592 |
| 10^6 |
78,498 |
| 10^7 |
664,579 |
| 10^8 |
5,761,455 |
| 10^9 |
50,847,534 |
- 錄驗附用法與果。
得:諸結獨驗無異。
敗:驗示異→重行原算開額察(如試除詳記)。常誤:篩限差一、模算整溢、誤偽素為素。
驗
忌
忘 n = 1 非素:例 1 既非素亦非合。諸算默誤分
模冪整溢:Miller-Rabin 算 a^d mod n 樸冪致溢。用模冪(重方各步取模)
篩差一誤:篩標合自 p^2 始非 2p。自 2p 浪時但正;自 p+1 誤
Pollard rho 環 d = n:gcd(|x - y|, n) = n→算得平因。試異多項常 c,非異始點
Carmichael 數欺 Fermat 測:561 = 3 * 11 * 17 等過諸互素基之 Fermat 素測。恆用 Miller-Rabin 非平 Fermat
混 pi(n) 與常 pi:素計函 pi(n) 與圓常 3.14159… 共記。脈須無歧
參
solve-modular-arithmetic —— 模算為 Miller-Rabin 與諸分解法之基
explore-diophantine-equations —— 素分為解多 Diophantine 方之前置
formulate-quantum-problem —— Shor 整分算接素於量算
1---2name: analyze-prime-numbers-93description: Analyze prime numbers using primality tests, factorization algorithms, prime distribution analysis, and sieve methods. Covers trial division, Miller-Rabin, Sieve of Eratosthenes, and the Prime Number Theorem. Use when determining whether an integer is prime or composite, finding prime factorizations, counting or listing primes up to a bound, or investigating prime properties within a number-theoretic proof or computation.4license: MIT5---67# 析素89擇行算:素測、分解、分析。算驗結而合素定理。1011## 用1213- 判某整為素或合→用14- 求整全素分→用15- 限內計或列素→用16- 驗某範素定理近→用17- 數論證或算察素性→用1819## 入2021- **必**:析之整或分析之限22- **必**:類——素測、分解、分析23- **可**:偏算(試除、Miller-Rabin、Eratosthenes 篩、Pollard rho)24- **可**:出形證或唯算判25- **可**:出式(因樹、素列、計、表)2627## 行2829### 一:定類3031請分為三類擇算路。32331. **素測**:給整 n,判 n 為素否342. **分解**:給合 n,求其全素分353. **分析**:給限 N,析 N 內素(計、列、隙、密)3637錄類與入值。3839得:明分附入值錄。4041敗:入含糊(如「析 60」)→請用者明素測、分解、分析。合默為分解,疑素默為素確。4243### 二:施素測(若類=素測)4445按 n 大配算測 n 為素否。46471. **平案**:n < 2 非素。n = 2 或 3 為素。n 偶且 > 2 為合。48492. **小 n(n < 10^6)**:用試除。50 - 試除諸素 p 至 floor(sqrt(n))51 - 優:試 2、後奇 3、5、7…或用 6k +/- 1 輪52 - 無除則 n 素53543. **大 n(n >= 10^6)**:用 Miller-Rabin 概測。55 - 書 n - 1 = 2^s * d,d 奇56 - 各證 a 於 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}:57 - 算 x = a^d mod n58 - x = 1 或 x = n - 1→此證過59 - 否方 x 至 s - 1 次。x 嘗等 n - 1→過60 - 無過→n 合(a 為證)61 - n < 3.317 * 10^24 之 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 證為定62634. **錄判**:素或合,附證或證書。6465**首二十五素:**6667| Index | Prime | Index | Prime | Index | Prime |68|---|---|---|---|---|---|69| 1 | 2 | 10 | 29 | 19 | 67 |70| 2 | 3 | 11 | 31 | 20 | 71 |71| 3 | 5 | 12 | 37 | 21 | 73 |72| 4 | 7 | 13 | 41 | 22 | 79 |73| 5 | 11 | 14 | 43 | 23 | 83 |74| 6 | 13 | 15 | 47 | 24 | 89 |75| 7 | 17 | 16 | 53 | 25 | 97 |76| 8 | 19 | 17 | 59 | | |77| 9 | 23 | 18 | 61 | | |7879得:定答(素或合)附用算與所見證或除。8081敗:Miller-Rabin 報「概素」而需確→升至定測(如 AKS 或 ECPP)。試除算太慢→換 Miller-Rabin。8283### 三:施分解(若類=分解)8485全分 n 為其素冪分。86871. **以試除取小因**:88 - 除 2 盡,錄冪89 - 除奇素 3、5、7、11…至截(如 10^4 或小 n 之 sqrt(n))90 - 各除後更 n 為剩餘因91922. **若餘 > 1 且 < 10^12**:續試除至 sqrt(餘)。93943. **若餘 > 1 且 >= 10^12**:施 Pollard rho。95 - 擇 f(x) = x^2 + c (mod n) 隨 c96 - 用 Floyd 環察:x = f(x)、y = f(f(y))97 - 各步算 d = gcd(|x - y|, n)98 - 1 < d < n→d 為非平因。遞於 d 與 n/d99 - d = n→以異 c 重試1001014. **驗**:乘諸素因(附冪)確同原 n。各因素測。1021035. **以標式呈**:n = p1^a1 * p2^a2 * ... * pk^ak,p1 < p2 < ... < pk。104105**算複雜:**106107| Algorithm | Complexity | Best for |108|---|---|---|109| Trial division | O(sqrt(n)) | n < 10^12 |110| Pollard's rho | O(n^{1/4}) expected | n up to ~10^18 |111| Quadratic sieve | L(n)^{1+o(1)} | n up to ~10^50 |112| GNFS | L(n)^{(64/9)^{1/3}+o(1)} | n > 10^50 |113114得:標式之全素分,乘驗。115116敗:Pollard rho 多迭不得因(環察無非平 gcd)→試異 c(至少 5 次)。皆敗→餘或為素,以素測確。117118### 四:施分析(若類=分析)119120析 N 內素分。1211221. **以 Eratosthenes 篩生素**:123 - 建大 N + 1 之布陣,初為真124 - 設 0 與 1 為偽(非素)125 - 各 p 自 2 至 floor(sqrt(N)):126 - p 仍真→標諸倍 p^2、p^2 + p、p^2 + 2p…為偽127 - 收諸仍真之指1281292. **計素**:算 pi(N) = N 內素數。1301313. **比於素定理**:132 - PNT 近:pi(N) ~ N / ln(N)133 - 對數積近:Li(N) = integral from 2 to N of 1/ln(t) dt134 - 算相對誤:|pi(N) - N/ln(N)| / pi(N)1351364. **析素隙**(可):137 - 算連素隙138 - 報最大隙、均隙、雙生素(隙=2)139 - N 近均隙約 ln(N)1401415. **以表呈**:142143```text144Bound N: 1,000,000145pi(N): 78,498146N/ln(N): 72,382147Li(N): 78,628148Relative error (N/ln(N)): 7.79%149Relative error (Li(N)): 0.17%150Max prime gap: 148 (between 492113 and 492227)151Twin primes: 8,169 pairs152```153154得:素計附 PNT 比與可選隙析。155156敗:N 太大不能內存篩(N > 10^9)→用段篩按段處範。唯需計(非列)→用 Meissel-Lehmer 直算 pi(N)。157158### 五:算驗159160以獨法交核諸結。1611621. **素測**:試除用→以快 Miller-Rabin 驗(或反之)。知素查表或 OEIS 序。1631642. **分解**:乘諸因確同原入。獨測諸宣素因素性。1651663. **分析**:抽 3-5 篩出之數獨素測。比 pi(N) 於標基出版值(pi(10^k) k = 1, ..., 9)。167168**pi(N) 出版值:**169170| N | pi(N) |171|---|---|172| 10 | 4 |173| 100 | 25 |174| 1,000 | 168 |175| 10,000 | 1,229 |176| 100,000 | 9,592 |177| 10^6 | 78,498 |178| 10^7 | 664,579 |179| 10^8 | 5,761,455 |180| 10^9 | 50,847,534 |1811824. **錄驗**附用法與果。183184得:諸結獨驗無異。185186敗:驗示異→重行原算開額察(如試除詳記)。常誤:篩限差一、模算整溢、誤偽素為素。187188## 驗189190- [ ] 類正分(素、解、布)191- [ ] 算合入大192- [ ] 平案(n < 2、n = 2、偶 n)通算前處193- [ ] 素判定(非「概素」無修飾)194- [ ] 分解乘回原195- [ ] 諸宣素因皆素測196- [ ] 篩限含 sqrt(N) 覆以標合197- [ ] PNT 比用正式(N/ln(N) 或 Li(N))198- [ ] 結以獨法或於出版值驗199- [ ] 邊例(n = 0、1、2、負入)皆理200201## 忌202203- **忘 n = 1 非素**:例 1 既非素亦非合。諸算默誤分204205- **模冪整溢**:Miller-Rabin 算 a^d mod n 樸冪致溢。用模冪(重方各步取模)206207- **篩差一誤**:篩標合自 p^2 始非 2p。自 2p 浪時但正;自 p+1 誤208209- **Pollard rho 環 d = n**:gcd(|x - y|, n) = n→算得平因。試異多項常 c,非異始點210211- **Carmichael 數欺 Fermat 測**:561 = 3 * 11 * 17 等過諸互素基之 Fermat 素測。恆用 Miller-Rabin 非平 Fermat212213- **混 pi(n) 與常 pi**:素計函 pi(n) 與圓常 3.14159… 共記。脈須無歧214215## 參216217- `solve-modular-arithmetic` —— 模算為 Miller-Rabin 與諸分解法之基218- `explore-diophantine-equations` —— 素分為解多 Diophantine 方之前置219- `formulate-quantum-problem` —— Shor 整分算接素於量算