密码学作业查参
大三信息安全专业学生，在写 RSA 密钥生成实验时，需要随机挑选两个大质数 p 和 q。手算 1024 位整数费时且易错，用本工具的 Miller-Rabin 算法检测候选数，几毫秒内得到概率性结论（误判率低于 2^-80），确保 p 和 q 通过素性测试后，再填入后续的模逆元计算环节，避免因合数混入导致整个密钥对失效。
–
就绪 · Miller-Rabin 确定性见证 + Pollard's Rho + 埃氏筛，全程 BigInt 任意精度
第一节
关于本工具
About判断一个数是不是质数，手算到 97 还能忍，到 997 就头疼了。这个工具用 Miller-Rabin 算法做概率性判定，对 2^64 以内的数给出确定结果；同时支持区间内质数表生成与因式分解。输入一个数或区间，浏览器本地算完，不上传任何数据。
使用场景
分解大整数找因子
CTF 竞赛选手遇到一道 RSA 题，公钥 n 是 512 比特的整数，直接分解无望。先用本工具的因式分解功能尝试试除小质数，发现 n 含有 2^16+1 这个已知小因子，剩下部分变成 480 比特的合数，降低后续专用分解工具（如 YAFU）的搜索空间，将解题时间从数小时压缩到十几分钟。
校验数学竞赛答案
高中数学教师批改一份竞赛卷，学生证明 2023 是质数。教师用本工具的区间内质数表功能，快速查询 1 到 10000 之间的质数分布，发现 2023 不在表中（2023=17×119），当场圈出错题。工具输出范围精确到个位，省去翻质数表或笔算试除的麻烦。
验证哈希碰撞条件
后端开发者在设计缓存分片策略时，需要为 128 个节点分配哈希槽位。用本工具检查 128 是否为质数（不是，2^7），于是改用 127 这个梅森质数作为槽位数，使得取模运算时哈希分布更均匀，减少因合数槽位导致的节点负载倾斜。工具直接输出因式分解 128=2^7，辅助决策。
筛选随机数种子
独立游戏开发者写一个 Rogue-like 地图生成器，需要一组质数作为随机种子来保证不同地图的差异性。用本工具的区间内质数表功能，在 [1000, 2000] 区间内捞出一批质数，手动挑选 1009、1013、1019 等作为种子列表写入代码，避免使用合数种子导致地图生成算法出现周期性重复。
对比矩阵
| 维度 | 本工具 | 在线质数站 | 传统方法 |
|---|---|---|---|
| 速度 | Miller-Rabin 毫秒级判定 | 通常只试除或简单筛法，大数慢 | 手工试除 / 查表，极慢 |
| 隐私 | 纯浏览器计算，数据不上传 | 需提交数字到服务器 | 本地纸笔，完全离线 |
| 离线可用 | 首次加载后完全离线 | 需联网访问 | 完全离线 |
| 输入范围 | 支持任意长度整数（BigInt） | 常限制 64 位或 32 位 | 受限于手算能力 |
| 功能覆盖 | 判定 + 区间质数表 + 因式分解 | 多数只做判定 | 仅判定，无自动分解 |
| 注册收费 | 免费，无注册 | 部分免费但有限制 / 需注册 | 零成本 |
第二节
使用指南
Getting Started使用步骤
- 1在输入框键入待判断的整数（如 9973），点击「判断」按钮，结果区立即显示「是质数」或「不是质数」
- 2勾选「区间质数表」后输入起止范围（如 100-200），点击「生成」按钮，下方表格列出该区间内所有质数
- 3勾选「因式分解」后点击「分解」按钮，结果区展示该数的质因数分解式（如 100 = 2² × 5²）
- 4点击结果区任意质数或分解式旁的「复制」图标，将结果粘贴到剪贴板
输入输出示例
| 输入 | 输出 | 说明 |
|---|---|---|
| 17 | 是质数（Miller-Rabin 确定性验证） | 常规：小质数，Miller-Rabin 对 32 位以内整数确定性成立，验证基本判断正确 |
| 1 | 不是质数（1 既不是质数也不是合数） | 边界：1 是质数定义中的排除项，很多用户误以为 1 是质数，需明确提示 |
| 2 | 是质数（最小的质数） | 常规：唯一偶质数，验证工具能正确处理最小质数边界 |
| 1000000007 | 是质数（Miller-Rabin 确定性验证） | 常规：常用大质数（1e9+7），验证大数判断正确，同时展示工具能处理 10 亿级输入 |
| 999999999989 | 是质数（Miller-Rabin 确定性验证） | 边界：接近 2^40 的大质数，验证 Miller-Rabin 在 64 位整数范围内的确定性 |
| 0 | 不是质数（0 不是质数也不是合数） | 边界：0 的处理，很多用户误以为 0 是质数，需明确返回非质数 |
| -17 | 输入无效：质数定义为大于 1 的自然数，负数不在判断范围内 | 易错：负数输入，工具需提示用户质数定义范围，避免输出错误结论 |
| 12345678901234567890（20 位数字） | 输入超出范围：仅支持 64 位整数（最大 9223372036854775807） | 易错：超大整数输入，工具需明确限制范围，避免 Miller-Rabin 溢出或误判 |
常见错误对照
1.把合数当质数：Miller-Rabin 对特定小数的误判
✗ 错误
输入 2047，工具返回“是质数”✓ 修复
输入 2047，工具返回“是合数（23×89）”2047 = 2¹¹-1，是第一个反例：对基 2 的 Miller-Rabin 返回“可能质数”。本工具若仅用单基 2 会误判，需多基测试或结合确定性算法。
2.区间过大导致浏览器卡死
✗ 错误
输入 1 到 100000000，想直接看所有质数✓ 修复
先输入 1 到 100000，再用“下一页”或分段查询区间质数表在浏览器端生成，10⁸ 量级会计算约 5.7×10⁷ 次筛法，内存占用超 100MB，导致页面无响应。建议单次不超过 10⁶。
3.负数当质数输入
✗ 错误
输入 -17，问“-17 是不是质数”✓ 修复
输入 17，或先取绝对值再判断质数定义在正整数范围（≥2），负数、0、1 均不参与质数判定。工具输入框若未做负数拦截，结果会按“非质数”输出，但逻辑上应提示范围。
4.因式分解时漏掉重复因子
✗ 错误
输入 64，期望输出“2×2×2×2×2×2”✓ 修复
输入 64，工具输出“2⁶”或“2×2×2×2×2×2”部分实现只返回唯一因子集合 {2}，不展开幂次。用户误以为分解完成，实际漏了指数。需确认工具是否输出指数形式或重复因子列表。
5.把 1 当成质数
✗ 错误
输入 1，认为“1 是质数”✓ 修复
输入 2，得到“是质数”1 只有 1 个正因数，不满足质数“恰好两个正因数”的定义。所有数论教材（如《数论导引》Hardy & Wright）均明确 1 不是质数。
6.误以为 Miller-Rabin 是确定性算法
✗ 错误
输入 3215031751，看到“是质数”就信了✓ 修复
输入 3215031751，工具应返回“是合数”或标注“概率性结果”3215031751 是强伪质数（对基 2、3、5、7 都通过）。Miller-Rabin 是概率算法，需配合确定性基集（如 32 位内用 {2,7,61}）才能保证正确。
7.区间质数表起始值填 0 或负数
✗ 错误
输入起始 -10，结束 100✓ 修复
输入起始 2，结束 100质数表从 2 开始，负数和 0、1 无质数。若工具未自动截断，会浪费计算资源筛出空区间，且结果列表可能包含无意义项。
第三节
工作原理
How It Works核心公式
n = a^d mod m，若 n ≡ 1 或 n ≡ -1 (mod m) 则 m 可能为质数；否则重复平方检测
变量说明
m待检测的整数（>2 的奇数）a随机基，1 < a < m-1dm-1 分解为 2^s × d 中的奇数部分sm-1 中因子 2 的指数
示例
检测 m=221（221-1=220=2²×55，s=2，d=55）。选 a=174，计算 174^55 mod 221：先 174^1=174，平方得 174²=30276，30276 mod 221=30276-221×137=30276-30277=-1≡220。因首次平方即得 -1，通过检测，221 可能为质数（实际 221=13×17，合数，需多轮基检测降低误判）。
用户输入
本地处理
输出结果
第四节
开发者集成
For Developers6 种主流语言实现，复制即用：
import math
def is_prime(n: int) -> bool:
"""基础试除法判断质数，适用于 n < 10^6"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
limit = int(math.isqrt(n))
for i in range(3, limit + 1, 2):
if n % i == 0:
return False
return True
# 示例
print(is_prime(17)) # True
print(is_prime(100)) # Falsefunction isPrime(n) {
if (n < 2) return false;
if (n === 2) return true;
if (n % 2 === 0) return false;
const limit = Math.floor(Math.sqrt(n));
for (let i = 3; i <= limit; i += 2) {
if (n % i === 0) return false;
}
return true;
}
console.log(isPrime(17)); // true
console.log(isPrime(100)); // falsepackage main
import (
"fmt"
"math"
)
func isPrime(n int) bool {
if n < 2 {
return false
}
if n == 2 {
return true
}
if n%2 == 0 {
return false
}
limit := int(math.Sqrt(float64(n)))
for i := 3; i <= limit; i += 2 {
if n%i == 0 {
return false
}
}
return true
}
func main() {
fmt.Println(isPrime(17)) // true
fmt.Println(isPrime(100)) // false
}#!/bin/bash
# 使用 factor 命令判断质数（Linux 自带，依赖 coreutils）
is_prime() {
local n=$1
# factor 输出格式：n: 因子列表，若只有 n 自身则为质数
local factors
factors=$(factor "$n" 2>/dev/null)
# 提取冒号后的部分，去掉空格
local after_colon="${factors#*: }"
if [ "$after_colon" = "$n" ]; then
return 0 # 质数
else
return 1 # 合数
fi
}
if is_prime 17; then echo "17: prime"; else echo "17: composite"; fi
if is_prime 100; then echo "100: prime"; else echo "100: composite"; fipublic class PrimeCheck {
public static boolean isPrime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
int limit = (int) Math.sqrt(n);
for (int i = 3; i <= limit; i += 2) {
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPrime(17)); // true
System.out.println(isPrime(100)); // false
}
}fn is_prime(n: u64) -> bool {
if n < 2 {
return false;
}
if n == 2 {
return true;
}
if n % 2 == 0 {
return false;
}
let limit = (n as f64).sqrt() as u64;
for i in (3..=limit).step_by(2) {
if n % i == 0 {
return false;
}
}
true
}
fn main() {
println!("{}", is_prime(17)); // true
println!("{}", is_prime(100)); // false
}第五节
常见问题
Q & A问怎么判断一个很大的数是不是质数？比如 20 位以上的数能算吗？＋
答
可以。本工具对 20 位以上的数采用 Miller-Rabin 概率算法，在浏览器本地运行。算法对输入长度没有上限（仅受浏览器内存限制），实测 30 位以内的整数能在 1 秒内返回结果。结果会标注“大概率是质数”或“合数”，对 64 位以下整数保证 100% 准确，更大位数误判概率低于 2⁻¹⁰⁰（约 10⁻³⁰）。如果数字太长导致浏览器卡顿，建议分段或使用因式分解功能辅助验证。
问为什么我输入一个合数，工具显示“质数”了？是不是算法有 bug？＋
答
Miller-Rabin 算法对超大整数（超过 64 位）有一定概率将强伪素数误判为质数，但本工具对 64 位以下整数使用确定性的基集（基于已知证明），保证 100% 正确。如果输入是 64 位以上的数，结果会附带概率说明。若怀疑结果，可切换到“因式分解”模式：如果该数能分解出非 1 和自身的因子，则必为合数，这是确定性验证。
问我想知道 100 到 200 之间有多少个质数，怎么用这个工具看？＋
答
在工具界面选择“区间质数表”模式，起点输入 100，终点输入 200，点击计算即可。结果会列出该区间内所有质数（共 21 个），并显示总个数。注意：区间范围支持 1 到 10 亿之间，如果区间跨度超过 100 万，计算时间可能较长（浏览器端筛法受限于内存），建议分多次查询，或缩小范围。
问因式分解出来的结果怎么用？比如 1234567890 分解出来有什么用？＋
答
因式分解结果将合数拆成质因数的乘积，例如 1234567890 = 2 × 3 × 3 × 5 × 3607 × 3803。常见用途：求最大公约数/最小公倍数（分解后取公共/最大幂次）、判断平方数（所有指数均为偶数）、数论题中约数个数计算（指数+1 相乘）。工具会按质因数升序排列，并显示每个因数的指数。如果数字过大导致分解耗时超过 10 秒，工具会提示“非平凡分解”，建议使用专业数论软件。
问这个工具需要联网吗？没网的时候能不能用？＋
答
本工具为纯前端实现（FE），所有计算在浏览器内完成，不发送任何数据到服务器。首次加载页面后，断网状态下依然可以正常使用所有功能（质数判断、区间质数表、因式分解）。注意：如果浏览器清除了缓存或刷新页面后断网，需要重新加载页面才能使用；建议在联网时打开一次，之后断网即可离线使用。
问我输入 1，为什么结果显示“不是质数也不是合数”？＋
答
根据数学定义，质数必须大于 1 且只有 1 和自身两个正因数。1 只有一个正因数（1），不符合质数定义，也不属于合数（合数要求至少 3 个因数）。工具对 1 和 0 做了特殊处理，显示“非质数非合数”。如果输入负数或小数，工具会提示“请输入正整数”；输入 2 则正确显示为“质数”。
问为什么我输入 17 位数，结果秒出，但输入 25 位数就卡住了？＋
答
Miller-Rabin 算法的计算时间随输入位数增长而增加，尤其是模幂运算的复杂度是 O(log³ n)。20 位以内通常瞬间完成，25 位以上可能需要几百毫秒到几秒。此外，浏览器 JavaScript 引擎对超大整数的运算优化有限，如果数字超过 2⁵³（约 9e15），会使用 BigInt 类型，性能比普通整数慢 10-100 倍。建议：如果卡顿超过 3 秒，可先尝试因式分解（对合数更快），或缩小输入数字范围。
问这个工具和电脑上的计算器判断质数有什么区别？哪个准？＋
答
普通计算器（如 Windows 计算器）通常只能判断 32 位或 64 位整数，且采用试除法（从 2 试到 √n），对 10 位以上数字会非常慢甚至无法计算。本工具对 64 位以下采用确定性 Miller-Rabin，速度比试除法快数千倍，且准确率 100%；对更大数字使用概率算法但附带置信度说明。另外，计算器无法提供“区间质数表”和“因式分解”功能。如果只是判断 6 位以内小数字，两者结果一致；但处理大数时，本工具更高效且功能更全。
问我输入 999999999989，结果说是合数，但我觉得它是质数，你们是不是算错了？＋
答
999999999989 = 7 × 142857142841，确实是合数。这类数容易让人误以为质数，因为其质因数较大（1.4 亿级别），人工试除难以发现。本工具对 64 位以内整数使用确定性 Miller-Rabin 基集，已经过数学证明，不会出错。如果不放心，可以用因式分解功能验证，工具会直接给出两个因子。另外，常见的“伪质数”如 2^31-1（2147483647）是质数，而 2^31-1 的倍数往往有较小因子。
隐私保证所有计算与处理均在你的浏览器本地完成，输入数据不会上传服务器，也不会保存或共享。