java - 计算非常大的 JAVA 的 Eulers Totient 函数

Question

我已经设法让 Eulers Totient Function 的一个版本工作，尽管它适用于较小的数字(与我需要它计算的 1024 位数字相比，此处较小的数字更小)

我的版本在这里-

public static BigInteger eulerTotientBigInt(BigInteger calculate) { 

    BigInteger count = new BigInteger("0");
    for(BigInteger i = new BigInteger("1"); i.compareTo(calculate) < 0; i = i.add(BigInteger.ONE)) { 
        BigInteger check = GCD(calculate,i);

        if(check.compareTo(BigInteger.ONE)==0)  {//coprime
            count = count.add(BigInteger.ONE);          
        }
    }
    return count;
}

虽然这适用于较小的数字，但它通过从 1 到正在计算的数字遍历每个可能的数字来工作。对于大的 BigIntegers，这是完全不可行的。

我读到过可以在每次迭代中对数字进行除法，从而无需逐一检查它们。我只是不确定我应该除以什么(我看过的一些例子是在 C 中使用 longs 和平方根 - 据我所知我无法计算准确的准确BigInteger 的平方根。我还想知道，如果对于像这样的模运算，该函数是否需要包含一个参数来说明 mod 是什么。我对此完全不确定，所以非常感谢任何建议。

谁能给我指明正确的方向？

PS 我在找到modifying Euler Totient Function 时删除了这个问题.我调整它以与 BigIntegers 一起工作 -

public static BigInteger etfBig(BigInteger n) {

    BigInteger result = n;
    BigInteger i;

    for(i = new BigInteger("2"); (i.multiply(i)).compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
         if((n.mod(i)).compareTo(BigInteger.ZERO) == 0) 
         result = result.divide(i);
         while(n.mod(i).compareTo(BigInteger.ZERO)== 0 ) 
             n = n.divide(i);
     }      
 if(n.compareTo(BigInteger.ONE) > 0)
 result = result.subtract((result.divide(n)));
 return result;
}

它确实给出了一个准确的结果，当传递一个 1024 位数字时它会永远运行(我仍然不确定它是否完成，它已经运行了 20 分钟)。

Answer 1

totient 函数有一个公式，需要对 n 进行质因数分解。看here .

公式为:

phi(n) = n * (p1 - 1) / p1 * (p2 - 1) / p2 ....
were p1, p2, etc. are all the prime divisors of n.

请注意，您只需要 BigInteger，而不是 float ，因为除法总是精确的。

所以现在问题简化为找到所有素因子，这比迭代要好。

这是完整的解决方案:

int n;  //this is the number you want to find the totient of
int tot = n; //this will be the totient at the end of the sample
for (int p = 2; p*p <= n; p++)
{
    if (n%p==0)
    {
        tot /= p;
        tot *= (p-1);
        while ( n % p == 0 ) 
            n /= p;
    }
}
if ( n > 1 ) { // now n is the largest prime divisor
    tot /= n;
    tot *= (n-1);
}