c++ - 欧拉的巨数披

Question

计算小数的欧拉 phi 很容易，甚至有许多在线站点提供此类功能。但是当数字真的很大时怎么办，我的意思是像 2^128？我如何计算如此大的 eulers phi 函数？我可以使用我的台式电脑吗？

Answer 1

如果您知道主要因素，那么是的。但总的来说，你不能有效地做到这一点，至少不是以任何人都知道的方式。如果我们可以计算一般的 totient 函数，那么我们可以得到它 n = pq，其中 p 和 q 是素数，即 (p-1)(q-1)。所以 n - phi(n) = p + q - 1，然后我们知道 p+q = c。那么 (p+q)^2 = c^2，所以 p^2 + q^2 = c^2 - 2n。但是 (p-q)^2 = p^2 + q^2 - 2pq = c^2 - 4n。所以我们知道p+q和p-q，从中我们可以得到p和q。

这会破坏 RSA encryption