# 原根查找器

查找模 n 的原根：先判断 n 是否属于 {2, 4, p^k, 2p^k}（乘法群为循环群），再给出最小原根及其判别证书（对每个整除 φ(n) 的素数 q 都有 g^(φ/q) ≠ 1）、原根总数 φ(φ(n))，可列出最多 50 个原根，或验证指定候选 g 的阶是否等于 φ(n)。支持 n ≤ 10¹²。

> 标准页面: https://elysiatools.com/zh/tools/primitive-root-finder

- **分类:** Math & Numbers

- **关键词:** 原根, 乘法群, 循环群, 欧拉函数, 数论, 离散对数

## 概述

原根查找器用于计算模 n 的最小原根、原根总数 φ(φ(n)) 并提供判别证书。工具首先检验模数 n 是否满足循环群充要条件（n ∈ {2, 4, p^k, 2p^k}），支持快速枚举最多 50 个原根或单点验证指定候选数 g 的乘法阶，支持最大 n ≤ 10¹² 的数论计算。

## 输入项

- **模数 n** (text): 2 ≤ n ≤ 10¹² (trial-division factorization bound).
- **输出模式** (select)
- **候选 g（验证模式）** (text): Required when verifying; reduced modulo n automatically.

## 适用场景

- 在实现 Diffie-Hellman 密钥交换或 ElGamal 加密体系需要选择模群生成元时
- 在离散数学或初等数论学习中验证乘法群是否为循环群及计算元素的阶时
- 在数论变换（NTT）或离散对数算法中寻找满足条件的最小本原元或全部原根时

## 工作原理

- 分解模数 n 并判断其代数形式是否属于 {2, 4, p^k, 2p^k}，确认其模乘法群是否为循环群并计算欧拉函数值 φ(n)
- 对 φ(n) 进行素因子分解，得到所有整除 φ(n) 的素因数集合 {q₁_prime, q₂_prime, ...}
- 遍历或测试候选数 g，校验 gcd(g, n) = 1，并验证对所有素因数 q 均满足 g^(φ(n)/q) ≢ 1 (mod n) 作为判别证书
- 依据选择的模式输出最小原根、原根总数 φ(φ(n))、最多 50 个原根列表，或详细的单候选数验证判定

## 使用案例

- 密码学协议参数初始化：为公钥加密体制生成可靠的模数与乘法生成元
- 数论教学与作业验算：快速获取模 n 的最小原根、群结构判定及幂次判别证书
- 算法竞赛与竞赛数论：验证大模数下指定候选底数是否为原根，排查 NTT 变换基底错误

## 常见问题

### 哪些模数 n 存在原根？

根据高斯原根定理，仅当模数 n 为 2、4、p^k 或 2p^k（其中 p 为奇素数，k ≥ 1）时，模 n 乘法群才是循环群并存在原根。

### 原根判别证书的数学依据是什么？

若候选数 g 满足与 n 互素，且对 φ(n) 的每个素因子 q 都有 g^(φ(n)/q) ≢ 1 (mod n)，则可严格证明 g 的阶为 φ(n)，即 g 为原根。

### 模 n 最多可以有多少个原根？

如果模 n 存在原根，则模 n 的原根总数精确等于 φ(φ(n))，其中 φ 为欧拉函数。

### 列表模式最多可以输出多少个原根？

当选择“同时列出原根”模式时，工具最多列出前 50 个原根，同时会给出原根总数 φ(φ(n))。

### 该工具支持的最大模数 n 是多少？

支持模数范围为 2 ≤ n ≤ 10¹²。

## 相关工具

- [二次剩余判定器（Legendre / Jacobi 符号）](https://elysiatools.com/zh/tools/quadratic-residue-checker): 计算 Jacobi 符号 (a/n)（n 为奇数，可达 10¹⁸；素数时即 Legendre 符号）：素数模下 a^((n−1)/2) ≡ 1 判定为二次剩余，并用 Tonelli–Shanks（或 p ≡ 3 (mod 4) 时的直接公式）给出平方根 ±√a；符号为 −1 则 a 一定不是二次剩余。合数模下 Jacobi 符号只是必要条件：−1 证明非剩余，+1 不确定（n ≤ 10⁵ 时自动暴力枚举求真相）。经典例：10 是 mod 13 的二次剩余，根为 ±6。
- [血气酸碱失衡判读（AG / ΔAG 联合分析）](https://elysiatools.com/zh/tools/blood-gas-anion-gap): 对动脉血气进行系统性酸碱失衡判读，结合阴离子间隙（AG）和 delta-delta（ΔAG/ΔHCO₃⁻）检测混合性酸碱紊乱。步骤：①pH 分层（酸血症/正常/碱血症）；②原发紊乱识别（代酸/代碱/呼酸/呼碱）；③代偿检查（Winter 公式 PaCO₂=1.5×HCO₃+8±2、急/慢性呼酸碱的 HCO₃ 变化规则）；④AG = Na−Cl−HCO₃（±白蛋白校正）；⑤Delta ratio：<0.4 正常 AG 代酸，0.4–0.8 混合，1–2 纯高 AG 代酸，>2 高 AG 代酸+代碱。不同于已有的 anion-gap-calculator（仅算血清 AG），本工具做完整血气判读。来源 Emmett 2016、Kraut CJASN 2007、Rastegar 2007、LITFL、MDCalc、Adrogué NEJM 1998。不构成医疗建议。
- [DNA 浓度计算器（A260 吸光度法）](https://elysiatools.com/zh/tools/dna-concentration-a260): 用 A260 紫外吸光度法测定 DNA 浓度：浓度 (µg/mL) = A260 × 稀释倍数 × 转换系数 ÷ 光程 (cm)。经验系数：双链 DNA 1 OD = 50 µg/mL，单链 DNA 1 OD = 33 µg/mL（RNA 为 40，见配套 RNA 工具）。1 µg/mL = 1 ng/µL；输入洗脱体积即可得总量 µg。附带 0.1–1.5 线性范围判读：低于 0.1 噪声为主，高于 1.5 探测器可能饱和，需稀释重测。纯度请用 OD260/280 工具判断。来源：Marmur & Doty 1961/1962、Sambrook & Russell、Thermo Fisher NanoDrop 技术资料。仅供教学与实验规划，请以校准仪器为准。
- [OD260/230 纯度比计算器（盐/有机溶剂污染）](https://elysiatools.com/zh/tools/od260-230-ratio): 用 OD260/230 比值判断核酸样品的盐与有机溶剂污染——这是 260/280 检不出污染时的重要补充：纯核酸该比值为 2.0–2.2，低于 2.0 提示胍（TRIzol/柱试剂盒）、酚、碳水化合物、EDTA、高盐或 β-巯基乙醇残留；2.2–2.3 通常为可接受的缓冲液效应；高于 2.3 提示水/缓冲液假象需复测。可选填 A280 同时给出 OD260/280 交叉核对（DNA ~1.8、RNA ~2.0），一次读数覆盖两个纯度维度。读数低于 ~0.05 时比值不可靠。来源：Thermo Fisher T042、Sambrook & Russell、Manchester 1995。仅供教学与实验规划。
- [核酸纯度比计算器（OD260/280）](https://elysiatools.com/zh/tools/od260-280-ratio): 用 OD260/280 比值判断核酸样品纯度：核酸碱基在 260 nm 吸收最强，蛋白质芳香族氨基酸与酚类在 280 nm 附近吸收，因此 A260/A280 可诊断蛋白/酚污染。预期值：纯 DNA ≈ 1.8（可接受 1.7–2.0），纯 RNA ≈ 2.0（可接受 1.8–2.2）；DNA < 1.7 或 RNA < 1.8 提示蛋白/酚/胍污染，DNA > 2.0 提示 RNA 污染，RNA > 2.2 提示低离子强度缓冲液等测量假象。可选填 A230 计算次级比值 A260/A230（纯品 2.0–2.2，偏低提示胍/酚/碳水化合物/盐残留）。读数低于 ~0.05 时比值不可靠。来源：Manchester 1995、Sambrook & Russell、Thermo Fisher T042。仅供教学与实验规划。
- [RNA 浓度计算器（A260，1 OD = 40 µg/mL）](https://elysiatools.com/zh/tools/rna-concentration-a260): 用 A260 紫外吸光度法测定 RNA 浓度：浓度 (µg/mL) = A260 × 稀释倍数 × 40 ÷ 光程 (cm)。RNA 的经验系数为 1 OD = 40 µg/mL，介于双链 DNA（50）与单链 DNA（33）之间；常见操作失误是沿用 dsDNA 的 50，会高估 RNA 产量 25%。1 µg/mL = 1 ng/µL；输入洗脱体积即可得总量 µg。附带 0.1–1.5 线性范围判读；纯 RNA 的 OD260/280 应接近 2.0（DNA 约 1.8），纯度请用配套比值工具判断，操作注意无 RNase、置冰。来源：Marmur & Doty 1961/1962、Sambrook & Russell、Manchester 1995、Thermo Fisher NanoDrop。仅供教学与实验规划，请以校准仪器为准。
- [训练/测试集分层切分器](https://elysiatools.com/zh/tools/train-test-split-with-stratification): 读取 CSV/JSON 数据集,按目标列做分层抽样的 train/validation/test 切分(默认 70/15/15,随机种子可复现),或分层 k 折交叉验证;输出每折类别分布报告与偏差条、重复行泄漏检查、SMOTE 过采样预览(仅在训练折上做最近邻插值),并可导出各折 CSV 为 ZIP。
- [有效数字计算器](https://elysiatools.com/zh/tools/sig-fig-calculator): 统计数字中的有效数字位数，并按目标有效位数进行修约

## 示例

- [Web Python 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-python): Web Python 图像处理示例，使用 PIL/Pillow 包括读取、保存、缩放和格式转换
- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换
- [Web Rust 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-rust): Web Rust 图像处理示例，包括图像读取保存、缩放和格式转换