Euler的BIG数（128位）函数是否有快速算法？

Question

我需要获得一些随机生成的128位数的phi-function（Euler）。我尝试使用下面的代码，但计算机只是想太多了。

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