欧拉大数（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 or a quadratic sieve 这样的东西会更好，但是手写这些很难。使用图书馆可能更好。

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

primefac (Python 2) and labmath (Python 3) 包含一个二次筛，但它基于代码高尔夫答案的一个旧的、有点慢和错误的版本。如果您想要固定版本，则需要转到 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

欧拉大数（128位）的totient函数是否有快速算法？

Is there a fast algorithm for Euler's totient function of BIG numbers (128bit)?

python

math

bignum