为什么我们不能用Zeta函数来搜索RSA中的素因子呢？

Question

也许我搞错了，但如果Zeta函数是有效的计算和反转，如果Riemann的假设是正确的(看起来是这样)，我们就不能用Zeta函数有效地找出大数的素因子，并找到公钥的私钥吗？

Answer 1

我们不能用Zeta函数有效地找出大数的素因子，找到公钥RSA密钥的私钥吗？

简而言之：\zeta函数不允许访问单个素数(我不知道有任何公式)，所以即使我们有一种超快的计算方法，它也不能用来寻找素数。

• 例如，\zeta函数提供的访问权限是1和x之间的素数，即素数计数函数\pi(x)。在素数函数\pi(x)和Riemann \zeta函数的所有零\rho之间确实有一种关系：\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac 12}\ln(1-x^{{-2}}).在这里认为\psi_0(x)是一个非常接近\pi(x)的概念，但是它只是用比1对每个素数的另一个权重来计算质数，而重量是\log p。这是省略了细节，但它提供了想法。有关更高的精度，请参见这里。
• \zeta函数的欧拉积包含所有素数，但没有给出生成/查找素数的有效方法：\zeta(s) = \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}

Answer 2

首先，我不认为\zeta(s)计算效率那么高。为了素数理论的目的，我们对计算\zeta(s)的兴趣通常集中在临界线\mathrm{Re}s=1/2上，而黎曼-西格尔公式需要O(t^{1/2})项来计算\zeta(1/2+it)。有计算倍数值的速度，但不是显着的。

同样，我也不知道你所说的反向是什么意思。这个函数不是双射的(例如，我们知道很多地方它是零的)。

尽管如此，在保理方法中使用解析数论还是有一些想法的。如果可以近似于L(1,\chi_N)，Shanks的类群分解方法就可以加快(这里的L-function表示数字字段\mathbb Q(\sqrt N)，并且与\zeta(s)密切相关)。假设广义Riemann假设，Shanks设法减少了他的算法的运行时间，将N从O(N^{1/4+\epsilon})分解为O(N^{1/5+\epsilon})。如此复杂的因素不太可能影响大于几百位的数字，也无法与通用数域筛竞争。

有一些使用\zeta(s)本身的想法(例如，参见Sica最近的论文"带提示的保理“)，但这些方法很难接近20世纪70年代Shanks方法的复杂性( Sica论文有复杂性O(N^{1/3+\epsilon}))。