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

1.9.15

Finding The Order Of An Element Faster

So far I've described and implemented one way of finding the order of any element mod n when n is the product of two distinct odd primes but there is another, even faster algorithm that takes half the number of computations of the previous algorithm described in Generating Exponentiation Tables.

This new algorithm takes advantage of the fact that every second element after the element at index 2 is simply a multiple mod n, which can be used to arrive at the element's order roughly two times faster than the algorithm previously described.

For example, in row j of the exponentiation table of Z sub n, the element at column 2 is s0=j*j, the element at column 4 is s1 = t*j and so on until either si = 1 or si = j.  A count of the number of "jumps" reveals the order of the element and furthermore if si = j, then the order of the element is odd and if si = 1 then the order of the element is even.

Below is the new algorithm:
/* -------------------------------------------------  
 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 any a mod n for n = p*q where p,q > 2  
 ---------------------------------------------------- */  

function find_order_faster(n, a)
 {
 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;
 } 


And for reference, below is the algorithm described in Generating Exponentiation Tables:

/* -------------------------------------------------  
 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 any a mod n for n = p*q where p,q > 2  
 ---------------------------------------------------- */  

function find_order(n, a)
 {
  int anot = 1;
  int aa = a;
  int aaa = a*a;
  int coef = a - 1;
  int index = 0;
  int order = 2;
  while(index != 1)
  {
      index = (coef*(anot + aa + aaa) + anot) % n;
      anot = aa;
      aa = aaa;
      aaa = index; 
      order = order + 1;
  }
  return order;
 } 

Note: both of these algorithms will run into an infinite loop if GCD(n,a) is not equal to 1 so a simple check must be added at the beginning of each function to find if GCD(n,a) is not equal to 1, in which case n can easily be factored.

The worst case scenario in the number of iterations for this new algorithm find_order_faster(n,a) is phi(n)/4 since the algorithm makes jumps to every second element starting from a*a for a given element a such that GCD(a,n)=1. 


For very large input n this should be used to speed up the following part of find_order_faster(n,a):
cur = (next * cur)

Although technically speaking only 1 of these two integers can potentially be large, the "next" integer is always going to be the integer at index 2, which for small a is very negligible.

find_order_faster(n,a) is guaranteed to hit either 1 or a in phi(n)/4 iterations since the starting point of the algorithm is the element at index 2 of any row j so therefore the elements are shifted by 2, which is a phenomenon I first discussed in Exponentiation Tables in Z sub n.

In contrast, the starting point of for the old algorithm find_order(n,a) is 1 and so in the worst case scenario it must visit every element up to phi(n)/2 since phi(n)/2 is a universal exponent as shown in Finding Phi.

Example: find_order_faster(35,3) returns 12 and visits only 9, 11, 29, 16, 4, 1:



  The iterations that find_order_faster(35, 3) makes

find_order(35,3), on the other hand, visits 3, 9, 27, 11, 33, 29, 17, 16, 13, 4, 12, 1

The above example shows the find_order_faster function's behaviour when the order of a is even: namely it terminates when it hits the first 1. If the order is odd  find_order_faster(n,a) will terminate as soon as it hits a and hence the if(cur == a){order = order - 1;} statement in the end but the number of iterations in this case will still be nearly half the number of iterations of find_order(n,a).

find_order(n,a) will behave the same way regardless of whether the order is even or odd.

The implementations of both algorithms with worker.js are shown below, and both of them are much faster now that strict types have been forced. Who knew Javascript isn't just some magical place where types just figure themselves out, slowing down everything else in the process.

Example: n = 3340291861
The find_order_faster(n) algorithm returns the order of 2 mod 3340291861 in 36 seconds and the algorithm find_order(n) returns it in 57 seconds using worker.js


The algorithm described in this post with a worker:


The algorithm described in Generating Exponentiation Tables with a worker:


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

31.8.15

The Art Of Overcounting

The function find_phi(n) pops up in almost all of my algorithms for finding phi of n, and almost always I point out that it is a function that may overcount.

Here's what I mean by that: if the order k of an element a mod n is less than the difference between n and phi(n) then the result from find_phi(n) will be a higher multiple of k than phi(n). In other words:

If k < (n - phi(n)) where ak = 1 mod n and k is the smallest such integer for a, then find_phi(n) returns  r such that r > phi(n) and (r-k)= phi(n)

Example:  Let p = 7 and q = 13 then n = p*q = 91 and let a = 2. Since n is the product of 2 distinct odd primes, then any of my functions for finding the order of 2 mod n described in Generating Exponentiation Tables and Phi Not Pi (neither of which uses exponentiation) will return k = 12
Since phi(n) = (p-1)(q-1) then in this case phi(91) = 72 but find_phi(91) returns 84 so r = 84, and as predicted (r-k) = 84 - 12 = 72 = phi(n)

In such a case where the order k of an element a mod n is less than the difference between n and phi(n) some manual poking will be required to retrieve phi(n) using find_phi(n), namely the order of 2 mod n must be returned along with the result of find_phi(n) so that it can be subtracted until phi(n) is reached but there are other functions for finding phi of n once the order of a particular element is known.

The most crucial piece of the puzzle in finding phi(n) is finding the order of an element mod n fast enough where "fast enough" is a relative concept.