c++ - 大数的欧拉 Phi

Question

它很容易计算小数的欧拉 phi，甚至有很多在线网站提供这样的功能。但是当数字真的很大时，我的意思是 2^128 怎么办？如何计算如此高的欧拉 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。但是然后 (pq)^2 = p^2 + q^2 - 2pq = c^2 - 4n。所以我们知道 p+q 和 pq，从中我们可以得到 p 和 q。

这会破坏RSA 加密