Euler Phi巨大的数字

它很容易计算小数字eulers phi，甚至有很多在线网站提供这样的功能。但是当数字真的很大时，我的意思是2^128？我怎样才能计算出这么高数量的eulers phi函数？我可以使用我的台式电脑吗？Euler Phi巨大的数字

2016-12-05 Sick654

在互联网上搜索“C++大号码库”和“C++多倍库”。 –

就使用您的台式电脑而言，取决于内存容量。巨大的数字比标准数字需要更多的内存。另外，取决于您拥有多少数据以及需要执行多少处理。这也取决于工具。如果你的电脑上有开发软件的工具，你可以使用你的电脑。 –

让我们都希望你不会很快找到桌面解决方案。 – molbdnilo

如果你知道主要因素，那么是的。但总的来说，你不能有效地做到这一点，至少不能以任何人都知道的方式。如果我们可以计算一般的总体函数，那么我们可以得到它为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

来源

2016-12-05 18:40:42 aah

什么时候我有3个素数？我得到了2^290 * 29 * 53 =我的号码 – Sick654

@ Sick654您可以直接使用[Euler's product formula]（https://en.wikipedia.org/wiki/Euler's_totient_function），只有3个不同的素数简单。 – aah

Euler Phi巨大的数字

回答

相关问题