计算非常大数JAVA的Euler商函数

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中看到的一些例子是使用long和一个平方根 - 据我所知我无法准确准确地准确BigInteger的平方根.我也想知道如果对于像这样的模运算,函数是否需要包含一个说明mod是什么的参数.我完全不确定,所以任何建议都非常赞赏.

任何人都能指出我在正确的方向吗？

PS当我发现修改Euler Totient功能时,我删除了这个问题.我改编它与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的素数因子分解.你看这里.

公式是:

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);
}