5.2.15

Finding Phi Faster

In here I laid out an algorithm for finding phi of n, or φ(n),  when n is the product of two distinct odd primes but the algorithm entailed a lot of exponentiation and modular arithmetic, which plays well with small exponents but chokes on even a 4 digit n.

On the other hand, in this post I outlined a simple algorithm for finding the order of 2 mod n when n is the product of two distinct odd primes.


This simple algorithm is crucial in finding φ(n) because the order of 2 mod n is the smallest integer k such that

2k = 1 mod n

Furthermore, since k divides φ(n) then the following brand new algorithm can get to phi of n without modulus, and without exponentiation simply by generating the row at 2 up to k as described and cycling through that row until n is reached as follows:

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find the order of 2 mod n for n = p*q where p,q > 2 
 and use the order of 2 mod n to find phi(n)  
 ---------------------------------------------------- */  
function findO2(n)
{
var a = 2;
var i = 1;
while(a !== 1)
{
   a = a + a;
   i = i + 1;
   if (a > n){ a = a - n;}   
} 
return i;
}

function find_phi(n)
{
 var cycle_length = findO2(n);
 var phi_length = 0;
 while(phi_length < n)
 {
    phi_length =  phi_length + cycle_length;     
 } 
return phi_length - cycle_length;
}


The worst case scenario for find_phi(n) is the best case scenario for findO2(n) - it is when the order of 2 mod n is either of the form r where r = (p-1)/2 and p is one of the primes, of which n is composed as described in Types of Exponents.


Below is a quite leaky implementation of the algorithm in Javascript using a single webworker.

Note that this is a Javascript implementation and it is quite leaky but nevertheless it can handle up to a 10 digit n in less than 35 minutes, which is still quite impractical in the real world of really large n.

Note: The implementation works when n is the product of any two distinct odd primes: safe primes, strong primes, sexy primes, you name it.