为非常大的数字计算Eulers Totient函数JAVA

我设法得到了Eulers Totient Function的一个版本，尽管它适用于较小的数字（与我需要计算的1024位数相比较小）为非常大的数字计算Eulers Totient函数JAVA

我的版本是在这里 -

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语言编写的，使用长整数和平方根 - 据我所知，我无法准确计算一个准确的数值我也想知道如果对于这样的模块化算法，函数是否需要包含一个说明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分钟）。

来源

2012-11-04 Saf

过分简化，你必须能够因子n来计算1024位数的总功能。在涉及计算总功能的加密协议中，您已经有了总分解。 –

你试图写该算法相当于融通说法n，这意味着你应该期望它永远运行下去，实际上讲，直到您的计算机死亡或你完蛋了。有关更多信息，请参见mathoverflow的本文：How hard is it to compute the Euler totient function?。

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

来源

2012-11-05 01:40:10 eh9

你完全正确，谢谢。抛出我的是我们笔记中的一条线，表示N = 55 = 5 x 11.我正在读这意味着他计算了55，但现在我看到了你的答案，很显然他选择了两个共素数来产生N. 感谢您的帮助:) – Saf

有一个总函数的公式，它需要n的素因子分解。 Look here。

其计算公式为：

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-04 07:28:37

这是否意味着如果我使用n-1作为p1（n是素数，所以phi n = n-1），那么p2等将成为我正在寻找的素数？或者它会返回主要因子的数量吗？ – Saf

我不知道我明白你的问题是什么... –

我的意思是说，你如何得到p1 p2等n的主要因子？或者他们是通过计算上面提到的phi（n）来给出的。 – Saf

etfBig方法有问题。
对于所有因素，欧拉的乘积公式是n *（（因子-1） /因子）。注：斯托的代码具有它为：

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

在etfBig法，用

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

测试从2至200随后产生相同的结果作为常规算法替换result = result.divide(i); 。

来源

2016-03-23 18:30:21 Tom

为非常大的数字计算Eulers Totient函数JAVA

回答

相关问题