Pohlig-Hellman 算法计算器

Q: Pohlig-Hellman 算法的计算公式是什么？

x ≡ xᵢ (mod qᵢ^eᵢ)（qᵢ^eᵢ ‖ p−1），CRT 合并得 x (mod p−1)。 复杂度由 p−1 的最大素因子决定：全平滑（各因子 < 2³⁰）时可在多项式时间内求解。 在Pohlig-Hellman 算法计算器中输入参数即可按此公式自动求解，无需手工推导。

Q: Pohlig-Hellman 算法有哪些容易忽略的细节？

每个素数幂子问题内部仍用 BSGS 或逐位法求解，规模 O(√q)；g 必须生成包含 h 的子群；h ∉ ⟨g⟩ 时残差无解。 其余细节见页面注意事项一节。

Q: 有没有Pohlig-Hellman 算法的实例演算？

平滑模数例：3^x ≡ 26 (mod 31)：p−1 = 30 = 2×3×5，各残差合并得 x = 5，验证 3⁵ = 243 ≡ 26 (mod 31) ✓。

Q: 怎么使用Pohlig-Hellman 算法？

首先，输入 g、h、素数 p（p−1 的素因子 ≤ 10⁵ 以便快速分解），点击计算。 然后，工具输出 p−1 的分解、每个素数幂的残差 x mod q^e、CRT 合并的 x，并回代验证。 全程在页面内完成，结果即时更新。

Q: Pohlig-Hellman 算法与大步小步算法是什么关系？

两者同属相关计算链条：大步小步算法解决的是与之衔接的另一层问题。完成Pohlig-Hellman 算法计算后，页面底部相关推荐区可直接跳转到大步小步算法计算器继续演算，参数在同类工具间口径一致，交叉验证更方便。

Q: 再举一个Pohlig-Hellman 算法的例子？

反例警示：若 p = 2q+1 且 q 是 160 位素数（安全素数），Pohlig-Hellman 无隙可乘——这正是密码学偏好安全素数的原因。

Q: Pohlig-Hellman 算法的输入有什么要求？

输入 g、h、素数 p（p−1 的素因子 ≤ 10⁵ 以便快。超出合理范围的输入可能导致结果无实际意义，页面注意事项一节标明了边界条件与单位口径。

Q: 怎么确认Pohlig-Hellman 算法的结果是准确的？

本页Pohlig-Hellman 算法计算器与页面内的公式、示例、对照表同源，全部数字由同一套程序实时计算。可用一个已知算例代入验证：先在示例一节找到演算过程，再用相同参数在计算器中复算一遍，两次结果一致即说明口径无误。

Q: Pohlig-Hellman 算法计算精度如何？

计算过程按双精度浮点执行，结果默认保留 4 位有效小数，页面会按数值大小自动切换科学计数法。对照表中的数值与计算器输出完全同源，不存在手工四舍五入引入的偏差。

什么是Pohlig-Hellman 离散对数？

Pohlig-Hellman 算法（1978）利用群同态把离散对数「化整为零」：对 p−1 的每个素因子幂 q^e，把方程两边升到余因子次幂，得到规模仅 q^e 的子群上的离散对数；逐位确定后用中国剩余定理合并。它说明：离散对数的安全性不取决于 p 多大，而取决于 p−1 的最大素因子多大。

x ≡ xᵢ (mod qᵢ^eᵢ)（qᵢ^eᵢ ‖ p−1），CRT 合并得 x (mod p−1)

复杂度由 p−1 的最大素因子决定：全平滑（各因子 < 2³⁰）时可在多项式时间内求解。

如何使用Pohlig-Hellman 离散对数

1
输入 g、h、素数 p（p−1 的素因子 ≤ 10⁵ 以便快速分解），点击计算。
2
工具输出 p−1 的分解、每个素数幂的残差 x mod q^e、CRT 合并的 x，并回代验证。

计算示例

例 1平滑模数例

3^x ≡ 26 (mod 31)：p−1 = 30 = 2×3×5，各残差合并得 x = 5，验证 3⁵ = 243 ≡ 26 (mod 31) ✓。

例 2反例警示

若 p = 2q+1 且 q 是 160 位素数（安全素数），Pohlig-Hellman 无隙可乘——这正是密码学偏好安全素数的原因。

注意事项

每个素数幂子问题内部仍用 BSGS 或逐位法求解，规模 O(√q)。
g 必须生成包含 h 的子群；h ∉ ⟨g⟩ 时残差无解。
本工具 p ≤ 10⁶，重在演示拆解过程；密码学规模的实现需数域筛级别算法。

常见问题

x ≡ xᵢ (mod qᵢ^eᵢ)（qᵢ^eᵢ ‖ p−1），CRT 合并得 x (mod p−1)。复杂度由 p−1 的最大素因子决定：全平滑（各因子 < 2³⁰）时可在多项式时间内求解。在Pohlig-Hellman 算法计算器中输入参数即可按此公式自动求解，无需手工推导。

每个素数幂子问题内部仍用 BSGS 或逐位法求解，规模 O(√q)；g 必须生成包含 h 的子群；h ∉ ⟨g⟩ 时残差无解。其余细节见页面注意事项一节。

平滑模数例：3^x ≡ 26 (mod 31)：p−1 = 30 = 2×3×5，各残差合并得 x = 5，验证 3⁵ = 243 ≡ 26 (mod 31) ✓。

首先，输入 g、h、素数 p（p−1 的素因子 ≤ 10⁵ 以便快速分解），点击计算。然后，工具输出 p−1 的分解、每个素数幂的残差 x mod q^e、CRT 合并的 x，并回代验证。全程在页面内完成，结果即时更新。

Pohlig-Hellman 算法（1978）利用群同态把离散对数「化整为零」：对 p−1 的每个素因子幂 q^e，把方程两边升到余因子次幂，得到规模仅 q^e 的子群上的离散对数；逐位确定后用中国剩余定理合并。它说明：离散对数的安全性不取决于 p 多大，而取决于 p−1 的最大素因子多大。

两者同属相关计算链条：大步小步算法解决的是与之衔接的另一层问题。完成Pohlig-Hellman 算法计算后，页面底部相关推荐区可直接跳转到大步小步算法计算器继续演算，参数在同类工具间口径一致，交叉验证更方便。

反例警示：若 p = 2q+1 且 q 是 160 位素数（安全素数），Pohlig-Hellman 无隙可乘——这正是密码学偏好安全素数的原因。

输入 g、h、素数 p（p−1 的素因子 ≤ 10⁵ 以便快。超出合理范围的输入可能导致结果无实际意义，页面注意事项一节标明了边界条件与单位口径。

本页Pohlig-Hellman 算法计算器与页面内的公式、示例、对照表同源，全部数字由同一套程序实时计算。可用一个已知算例代入验证：先在示例一节找到演算过程，再用相同参数在计算器中复算一遍，两次结果一致即说明口径无误。

计算过程按双精度浮点执行，结果默认保留 4 位有效小数，页面会按数值大小自动切换科学计数法。对照表中的数值与计算器输出完全同源，不存在手工四舍五入引入的偏差。

若整数的所有素因子都不超过 B，称其为 B-平滑。p−1 若是 B-平滑且 B 不大，Pohlig-Hellman 就能高效求解离散对数。

同一批作者 1978 年还提出了 Pohlig-Hellman 密码系统（模素数的指数密码）；RSA 的安全性同样依赖大数分解困难，两者共享「难问题构造公钥」的思想。

参考资料

凯文内容作者Calcton 数学编辑组口径审核Calcton 编辑组交叉审核· 内容更新于 2026-09-16

负责 Calcton 的公式核对与内容撰写：每个工具的公式都注明出处，示例数字经过程序复算，健康与判定标准一律采用国际口径。

Calcton 数学编辑组：标准教科书（高中至大学低年级）与常用数学手册的公式口径。

参考来源与更新说明

本页公式与判定标准参考以下权威资料：

最后更新：2026-09-16。

免责声明：本页面提供的计算结果与说明内容仅供参考，不构成医疗、税务、投资或法律等专业建议。尽管我们力求公式与数据准确，仍可能存在误差；据此做出的任何决策，请结合专业机构意见。

Pohlig-Hellman 离散对数

什么是Pohlig-Hellman 离散对数？

如何使用Pohlig-Hellman 离散对数

计算示例

注意事项

常见问题

参考资料

引用本页

把这个计算器嵌入到你的网站

参考来源与更新说明

什么是Pohlig-Hellman 离散对数？

如何使用Pohlig-Hellman 离散对数

计算示例

注意事项

常见问题

Pohlig-Hellman 算法的计算公式是什么？

Pohlig-Hellman 算法有哪些容易忽略的细节？

有没有Pohlig-Hellman 算法的实例演算？

怎么使用Pohlig-Hellman 算法？

什么时候需要用Pohlig-Hellman 算法？

Pohlig-Hellman 算法与大步小步算法是什么关系？

再举一个Pohlig-Hellman 算法的例子？

Pohlig-Hellman 算法的输入有什么要求？

怎么确认Pohlig-Hellman 算法的结果是准确的？

Pohlig-Hellman 算法计算精度如何？

「平滑」（smooth）是什么意思？

Pohlig-Hellman 与 RSA 有何关系？

参考资料

引用本页

把这个计算器嵌入到你的网站

相关计算器

参考来源与更新说明

搜索计算器