欧拉斯(Eulers Phi)数量很大

Question

易于计算少数数字的欧尔人，甚至还有许多在线站点提供此类功能。但是，当数字真的很大时，我的意思是2^128呢？如何计算如此高数字的Eulers PHI函数？我可以将桌面PC用于此吗？

Answer 1

如果您知道主要因素，则是。但是总的来说，您不能有效地做到这一点，至少不是任何人都知道的。如果我们可以一般计算基准函数，那么我们可以将其用于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加密