11.9.15

Finding The Order Of An Element Even Faster

The following algorithm is an optimized version of the algorithm presented here. Like the earlier
version, this algorithm also finds the order of an element by successively jumping over several elements at a time but this one jumps over 4 instead of just 2, which means it needs to iterate through only half the elements of find_order_faster(n, a) described in Finding The Order Of An Element Faster.

The logic behind this and the previous algorithm was first described in the last few paragraphs of Exponentiation Tables in Z sub n. I don't have to stop at 4 skips so long as I account for the overcount and keep the initial element a small and divisible by only itself and 1: in other words a big n requires a big jump but the result can be found in the same number of iterations as a smaller n.

For example, finding the order of a mod n for a 10 digit n can be reduced from 40 minutes to a few seconds simply by adjusting the length of the jump.

/* -------------------------------------------------  
 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_even_faster(n, a)
 {
   int aa = (a*a);  
   int aaa = (a*a*a);
   int aaaa = (a*a*a*a);
   int cur = aaaa;
   //length of the jump
   int index = 4;
   while ( cur !== 1 && cur !== a && cur !== aa && cur !== aaa)
   {
      cur = (aaaa * cur)%n;
      index = 4 + index;    
   }     
   if(cur === a){index = index-1;}
   else if(cur === aa){index = index-2;} 
   else if(cur === aaa){index = index-3;}
   return index;
 } 

Someone might be tempted to use a ternary operator to replace the if-else statements at the end but a ternary operator will be too costly in this case. Especially for bigger jumps where the number of if-else statements might exceed 100 million.

And below is the older algorithm, with cleaner variable names for reference. Looking at the two algorithms one might think of recursion to speed things up even more but I will not talk about this here.

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

Outside of the while loop of both algorithms there is a number of primitive operations, and this number is proportional to the length of the jump.

In the while loop of these algorithms there are 3 things happening, namely: finding the product of the current element times a predefined constant; finding the remainder of the two; counting the number of  jumps.

Standard multiplication of two n-bit integers takes O(n2) but there is an algorithm that uses only
O(n log2 n log2 log2 n) bit operations.

Finding the quotient of two integers can be done in the same number of bit operations as the number of bit operations needed to multiply two n-bit integers.

Counting the number of jumps is fairly trivial.

By the way, it is easy to see that standard multiplication of one n-bit integer and one m-bit integer takes O(mn)

The implementation below is in Javascript because I am a computational masochist.

The 4-skip implementation of the algorithm described earlier in this post with Javascript:



The 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript:



The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 3 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
  5.  Using quadruple skips

Note that in the last two algorithms if n is large and a is less than 1/4 of n with non-trivial order then aa and aaaa will be relatively small as well. Both algorithms will overcount trivial orders up to the jump length.