23.7.15

Generating Exponentiation Tables

I hinted at one way of generating exponentiation tables in the last post of the Life of Phi trilogy, which involved dealing with permutations but there's another interesting way of generating exponentiation tables that relies on the following observation:

Each entry aij in the exponentiation table with i rows and j columns  of Zn when n is the product of 2 distinct primes can be generated as follows:

aij = [(j - 1)(ai-1 + ai-2 + ai-3)] + ai-3  mod n

Below is an algorithm for finding the order of any element of the exponentiation table of Zn when n is the product of 2 distinct primes. It can easily be modified to generate the entire table recursively.

It's also fast.

/* -------------------------------------------------  
 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)
 {
  var anot = 1;
  var aa = a;
  var aaa = a*a;
  var coef = a - 1;
  var index = 0;
  var order = 2;
        //added bonus
  var bingo = "a divides n";
  
  while(index != 1)
  {
   if (index === a) {return bingo;}
   index = (coef*(anot + aa + aaa) + anot) % n;
   anot = aa;
   aa = aaa;
   aaa = index; 
   order = order + 1;
  }
  return order;
 } 


Example: The algorithm described in this post here and implemented with a worker finds it in 1:49 min whereas the algorithm implemented in Life of Phi and featured in Finding Phi Faster finds the order of 2 mod 915313319 in 2:20 min. The worker slows things down a bit, like quite a bit.

The above algorithm returns the correct answer for the order of 2 mod 915313319 in less than 20 seconds and only one "unresponsive script" nudge in the ribs required to return the correct result! What's more impressive is that find_order(n, a) can find the order of any element a of Zn if GCD(a, n) = 1 or find a zero divisor of Zn , and in particular it can find the order of 4 mod n much faster.

Indeed, in a web console find_order(n, a) returns the order of 4 mod 915313319 in less than 10 seconds!




For faster JS results, try find_order(n, a) in a web console. 

Below are a few slower JS implementations.

The algorithm described in this post with a worker:


The algorithm described in Life of Phi with a worker: