大数的欧拉φ
大数的欧拉φ
提问于 2016-12-06 02:13:40
它很容易计算小数字的eulersφ，甚至有许多在线网站提供这样的功能。但是当数字真的很大时，我的意思是像2^128？我如何计算这么高的eulersφ函数？我可以使用我的台式pc来做这件事吗？
回答 1
Stack Overflow用户
发布于 2016-12-06 02:40:42
如果你知道主因子，那么是的。但一般来说，你不能有效地做到这一点，至少不是以任何人都知道的方式。如果我们可以计算总体函数，那么我们可以得到n= pq，其中p和q是素数，它将是(p-1)(q-1)。所以n-φ(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
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40980680
复制相关文章
相似问题
腾讯云开发者
