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