25.7.15

Finding Phi Even Faster

Renote: phi(n) is the number of integers that are coprime with n; phi(n) = (p-1)(q-1) when n is the product of two distinct odd primes p and q. In Types of Exponents I showed that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes.

In Life of Phi I came up with one way of finding the order of 2 mod n when n is the product of two distinct odd primes, and then I used it in Finding Phi Faster to find phi(n).

A few days ago I uncovered a new way of finding the order of 2 mod n when n is the product of two distinct odd primes.

This means that there's yet another way of finding phi(n) that is even faster than the way described in
Finding Phi Faster using the new algorithm described in Generating Exponentiation Tables.

The algorithm below re-uses the same overcounting find_phi(n) function from Finding Phi Faster but the entire algorithm in this post finds phi(n) even faster because find_order(n) is faster than findO2(n).


/* -------------------------------------------------  
 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 it to find phi(n)   
 ---------------------------------------------------- */  

function find_order(n)
 {
  var a = 1;
  var aa = 2;
  var aaa = 4;
  var index = 0;
  var order = 2;
  while(index != 1)
  {
   index = (a + aa + aaa + a) % n;
   a = aa;
   aa = aaa;
   aaa = index; 
   order = order + 1;
  }
  return order;
 } 

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

Example: n = 8767703359 where n = p*q and p = 137483, q = 63773

Without worker.js the new algorithm finds phi(n) in less than 30 seconds whereas the old algorithm takes a couple of minutes.

With worker.js the new algorithm finds phi(n) in 18 : 58 whereas the old algorithm takes 25 : 7 !
Clearly worker.js is overworked and underpaid but that's not the point.

A few more examples below:

n = 12899*11483 = 148119217
n = 17327*34703 = 601298881
n = 55103*42767 = 2356590001    
n = 83243*40127 = 3340291861  
n = 62303*164999 = 10279932697  
n = 547357*195971 = 107266098647  
Below is an implementation of this new algorithm with worker.js followed by an implementation of the old algorithm with worker.js.

The algorithm described in this post with a worker:


The algorithm described in Finding Phi Faster with a worker: