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巨大的數字

回答

相關問題