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位数字,简单的试验分割将是非常低效的.像椭圆曲线分解或二次筛的东西会更好,但手工编写这些很难.使用库可能更好.

我发现的大数量因子分解算法的最佳Python实现是,不管你信不信,这个答案来自primo on codegolf.stackexchange.com.它是一个多项式二次筛.

primefac(Python 2)和labmath(Python 3)包含了一个二次筛子,但它基于Code Golf答案的一个旧的,有点慢和错误的版本.如果你想要固定版本,你会想要去Code Golf答案.(另外,注意,labmath.factorint默认为不使用实施MPQ格式压缩文件)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