4.9.15

Finding Phi Much Faster

So far I've come up with 4* different ways of finding the order of 2 mod n and 2 different ways of finding the order of any element a mod n such that GCD(a,n) = 1, all of which can be used to find phi(n).

The order of an element can be used to find phi(n) as I already showed in the first few Finding Phi posts. 

Here's the latest, fastest so far algorithm for finding phi(n) when n is the product of two distinct odd primes, which uses the algorithm described in here and the overcounting find_phi(n) function, but it doesn't use Discrete Fourier Transform for faster multiplication.

/* -------------------------------------------------  
 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_faster(n, 2)
 {
 int next = a*a;
 int cur = next;
 int order = 2;
 while( cur != a && cur != 1)
 {
      cur = (next * cur)%n;
      order = 2 + order;     
 }
 if(cur == a){order = order - 1;}
 return order;
 } 

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

Here's the implementation for the above algorithm using a worker that is not overworked now that it is only dealing with integers.

By the way, this is why it is important to enforce strict types in Javascript even though it supposedly takes care of things in the background with magic: in programming there's no such thing as magic and if someone claims the opposite, then beware.  



*The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 2 ways can be used for finding the order of any element mod n:
  1.  Using a cyclic permutation
  2.  Using an algebraic expression
  3.  Using simple addition
  4.  Using double skips