python - 欧拉大数(128位)的totient函数是否有快速算法？

Question

我需要获得一些随机生成的 128 位数字的 phi 函数(欧拉函数)。我尝试在下面使用这段代码，但计算机只是想得太多了。

import fractions

def phi(n):
    amount = 0        
    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1
    return amount

有没有更快的东西？

Answer 1

对于 128 位数字，您需要高效地计算 n 的质因数分解，然后使用

totient = n
for factor in prime_factors(n):
    totient -= totient // factor

---

困难的部分是分解。对于 128 位数字，简单的试除法效率极低。类似于 elliptic curve factorization或 quadratic sieve会更好，但是手写这些很难。使用库可能更好。

不管你信不信，我发现的大数分解算法的最佳 Python 实现是 this answer通过 primo在 codegolf.stackexchange.com 上。这是一个多项式二次筛。

primefac (Python 2)和 labmath (Python 3)包含一个二次筛，但它基于旧的、有点慢且有问题的 Code Golf 答案版本。如果您想要固定版本，则需要转到 Code Golf 答案。 (另外，请注意 labmath.factorint 默认不使用 mpqs 实现。)labmath 和 primefac 还包括椭圆曲线分解，以及很少有其他算法不太可能对这种输入大小有用。

除此之外，还有 sympy.ntheory.factorint , 但在我的测试中它有大因子的问题，它只有试验除法、pollard rho 和 pollard p-1 分解。

---

无论如何，使用这些现有的分解选项之一，或实现您自己的分解选项，或其他任何选项，然后在此基础上构建您的 totient 函数。例如，使用 primefac:

# primefac.factorint(n) returns a factor:multiplicity dict
from primefac import factorint

def totient(n):
    totient = n
    for factor in factorint(n):
        totient -= totient // factor
    return totient