Calculating Eulers Totient Function for very large numbers JAVA

Question

I've managed to get a version of Eulers Totient Function working, albeit one that works for smaller numbers (smaller here being smaller compared to the 1024 bit numbers I need it to calculate)

My version is here -

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

While this works for smaller numbers, it works by iterating through every possible from 1 to the number being calculated. With large BigIntegers, this is totally unfeasible.

I've read that it's possible to divide the number on each iteration, removing the need to go through them one by one. I'm just not sure what I'm supposed to divide by what (some of the examples I've looked at are in C and use longs and a square root - as far as I know I can't calculate an accurate an accurate square root of a BigInteger. I'm also wondering that if for modular arithmetic such as this, does the function need to include an argument stating what the mod is. I'm totally unsure on that so any advice much appreciated.

Can anyone point me in the right direction here?

PS I deleted this question when I found modifying Euler Totient Function. I adapted it to work with 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;
}

And it does give an accurate result, bit when passed a 1024 bit number it runs forever (I'm still not sure if it even finished, it's been running for 20 minutes).

Answer 1

The algorithm you are trying to write is equivalent to factoring the argument n, which means you should expect it to run forever, practically speaking until either your computer dies or you die. See this post in mathoverflow for more information: How hard is it to compute the Euler totient function?.

If, on the other hand, you want the value of the totient for some large number for which you have the factorization, pass the argument as sequence of (prime, exponent) pairs.

Answer 2

There is a formula for the totient function, which required the prime factorization of n. Look here.

The formula is:

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

Note that you only need BigInteger, not floating point, because the division is always exact.

So now the problem is reduced to finding all prime factors, which is better than iteration.

Here is the whole solution:

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

Answer 3

The etfBig method has a problem.
Euler's product formula is n*((factor-1)/factor) for all factors. Note: Petar's code has it as:

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

In the etfBig method, replace result = result.divide(i); with

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

Testing from 2 to 200 then produces the same results as the regular algorithm.