为大输入计算欧拉 Totient 函数的有效方法
Efficient way to compute Eulers Totient Function for big input
根据维基百科关于Euler's Totient Function的描述，我编写了以下代码：
from math import gcd
def phi(n):
amount = 0
for k in range(1, n + 1):
if gcd(n, k) == 1:
amount += 1
return amount
它适用于小数字，但我想计算数字的 totient 函数，例如
n = 5692297035794675412610596123456169
有没有更好的方法来计算大输入的 Totoent 函数？
由于这也被标记为密码学，因此这更多地涉及可能算法的有效性。
如果您知道 n 的质因数，那么有一种方法可以非常快速地计算欧拉总和 φ 。设 pi 是 n 的不同 k 个质因数，然后
φ(n) = (p1 -1) * (p2-1) * ... * (p k-1)
素数幂也有一个公式。这在这里没有必要，因为 RSA encryption/signature 或 Paillier 加密或 Rabin 签名使用 n = p*q 和两个不同的素数 p 和 q.
如我们所见，有效地找到 φ(n) 需要因式分解的知识。证明对于 RSA 来说，φ(n) 的知识等于 n 的因式分解。很快看到这里；
或见RSA原论文；
如果我们转向分解 (RSA)，目前的记录是在 2020 年取得的，CADO-NFS has factored an 828-bit n“大约 2700 个核心年，使用 Intel Xeon Gold 6130 CPU 作为参考 (2.1GHz)”。
但是，如果您需要使用 RSA，则应使用大小至少为 2048 位的模数，请参阅 keylength.com。至少在合理的时间内，从经典分解和 Shor 的量子分解算法中，这对于分解是安全的。
因此，如果您不知道因式分解，则没有有效的算法可以找到大 n 的欧拉总分。
根据维基百科关于Euler's Totient Function的描述，我编写了以下代码：
from math import gcd
def phi(n):
amount = 0
for k in range(1, n + 1):
if gcd(n, k) == 1:
amount += 1
return amount
它适用于小数字，但我想计算数字的 totient 函数，例如 n = 5692297035794675412610596123456169
有没有更好的方法来计算大输入的 Totoent 函数？
由于这也被标记为密码学，因此这更多地涉及可能算法的有效性。
如果您知道 n 的质因数，那么有一种方法可以非常快速地计算欧拉总和 φ 。设 pi 是 n 的不同 k 个质因数，然后
φ(n) = (p1 -1) * (p2-1) * ... * (p k-1)
素数幂也有一个公式。这在这里没有必要，因为 RSA encryption/signature 或 Paillier 加密或 Rabin 签名使用 n = p*q 和两个不同的素数 p 和 q.
如我们所见，有效地找到 φ(n) 需要因式分解的知识。证明对于 RSA 来说，φ(n) 的知识等于 n 的因式分解。很快看到这里；
或见RSA原论文；
如果我们转向分解 (RSA)，目前的记录是在 2020 年取得的，CADO-NFS has factored an 828-bit n“大约 2700 个核心年，使用 Intel Xeon Gold 6130 CPU 作为参考 (2.1GHz)”。
但是，如果您需要使用 RSA，则应使用大小至少为 2048 位的模数，请参阅 keylength.com。至少在合理的时间内，从经典分解和 Shor 的量子分解算法中，这对于分解是安全的。
因此，如果您不知道因式分解，则没有有效的算法可以找到大 n 的欧拉总分。