1

我已经设法使 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 到正在计算的数字的所有可能来工作。对于大的 BigInteger，这是完全不可行的。

我已经读过可以在每次迭代中划分数字，从而无需逐个遍历它们。我只是不确定我应该除以什么（我看过的一些示例是用 C 语言并使用 long 和平方根 - 据我所知，我无法计算出准确的BigInteger 的平方根。我还想知道，如果对于像这样的模运算，函数是否需要包含一个参数来说明 mod 是什么。我完全不确定，所以任何建议都非常感谢。

谁能在这里指出我正确的方向？

PS 当我发现修改 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 分钟）。

4

3 回答 3

10

totient 函数有一个公式，它需要对 n 进行素数分解。看这里。

公式为：

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

请注意，您只需要 BigInteger，而不是浮点数，因为除法始终是精确的。

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

这是整个解决方案：

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);
}
于 2012-11-04T07:28:37.880 回答
1

您尝试编写的算法相当于将参数分解n，这意味着您应该期望它永远运行，实际上直到您的计算机死机或您死机为止。有关更多信息，请参阅 mathoverflow 中的这篇文章：计算 Euler totient 函数有多难？.

另一方面，如果您想要某个具有因式分解的大数的总的值，请将参数作为（素数，指数）对的序列传递。

于 2012-11-05T01:40:10.987 回答
0

etfBig 方法有问题。
欧拉的乘积公式是所有因子的 n*( (factor-1) /factor)。注意：Petar 的代码如下：

tot /= p; tot *= (p-1);

在 etfBig 方法中，替换result = result.divide(i); 为

result = result.multiply(i.subtract(BigInteger.ONE)).divide(i);

然后从 2 到 200 进行测试会产生与常规算法相同的结果。

于 2016-03-23T18:30:21.763 回答