17.3.16

Exponentiation tables in Z sub power of a prime

I already discussed two different types of exponentiation tables, namely those of Zn where n is the product of two distinct odd primes p and q and of Zp when p is a prime.

Another interesting type of exponentiation tables is that of Zpk when p is prime and k is any integer. If p is prime then pk has a primitive root so the only universal exponent mod pk is strictly φ(pk). In this case this is equal to:

φ(pk) = pk − pk−1 = pk−1(p − 1)

Additionally, Zpk has elements i, j > 0 such that ij = 0 when i is any multiple of p. Therefore the rows i of the exponentiation table of Zpk  that are multiples of p are simply 0 for j > 1




Below is the exponentiation table of Z25  where p = 5 and k = 2. Note that 5 is a tough prime and the order of 2 mod n is the highest order as conjectured here.

Each entry at row i and column j is equal to  i^j mod 25

So if p is a tough prime, and the order of 2 mod pk is φ(pk) then this allows for the construction of the entire table without using multiplication, exponentiation, or modular arithmetic!

To do this I first borrow the 2 functions I described in here.

  1. Given an odd integer n list all even integers smaller than n, 
    followed by all odd integers smaller than n.
  2. a. Look up the value at initial index.
    b. Make that value the initial index.  
    c. Save the permutation and Repeat a and b until the value equals 1.  
And I add the following 2 functions:

3. Given a value k and a permutation as described in 2, find the index of the value in the permutation or return 0 if it is not there.
4. Given a permutation perm and an index i of a value v within the permutation:
 a. if index is 0 then add 0 to the row and recurse to the next row
 b. else make a pointer to the next value in row which has a distance i from v and so while next value is not 1, then recurse to next row

Below is the full algorithm in Javascript:
    /* -------------------------------------------------  
     This content is released under the GNU License  
     http://www.gnu.org/copyleft/gpl.html 
     Author: Marina Ibrishimova 
     Version: 1.0
     Purpose: Generate the unique portion of the 
     exponentiation table of Z sub n when n is 
     either a tough prime p or a power of tough prime
     ---------------------------------------------------- */  
    
    function powers_of_two_mod(n)
    {
     var index = 0;
     var perm_slot = 2;
     var count = 1;
     var perm = new Array(); var powers = new Array();
     perm = generate_permutation(n);
     powers.push(1);powers.push(perm_slot);
     while(perm_slot != 1)
     {
        index = perm_slot;
        perm_slot = perm[index];
        powers.push(perm_slot); 
     }
     return powers;
    }
    
    /* -----------------------------------------------
      list all even integers smaller than n,  
      followed by all odd integers smaller than n:
      this is 2nd row of the multiplication table of Z sub n
    -------------------------------------------------- */
    function generate_permutation(n)
    {
     var index = 0;
     var permutation = new Array();
     permutation.push(0);
     while(index<n)
     { 
       index = index + 2;
       if (index == n-1)  {
           permutation.push(index);
           index = 1;
       }
       permutation.push(index);
     }
     return permutation;
    }
    
    //find the index of a particular value within permutation
    function findindex(perm, k)
    {
        //not interested in value at index 0, which is 2
        //since the row at 2 is already found
     var index = 1;
     while(perm[index] != k) {
      if (index > perm.length) { return 0; }
      index = index + 1;
     }
     return index;  
    }
    
    //generate the entire exponentiation table
    function generate_table(perm, k, index, len, table, n)
    {
     var temp = index;
     table.push(1);
     table.push(k);
     k = k + 1;
     //only needed if n is a power of a prime
     if (index == 0) 
     {
      table.push(0);
       
      index = findindex(perm, k); 
      generate_table(perm, k, index, len, table, n);   
     }
     else
     {
     //permute the second row to get the other rows 
      while(perm[temp]!=1) 
      {
       temp = temp + index;
       if (temp > len){temp = temp - len;}
       table.push(perm[temp]);   
      } 
     //move onto next row 
      if( k <= (n - 1) )
      {
       
       index = findindex(perm, k);
       generate_table(perm, k, index, len, table, n); 
      }
     return table;
     }
    }
    
    

    Note: This algorithm works for generating the unique portion of  full exponentiation tables  of Zp when p is a tough prime and Zpk when p is a tough prime and k is any integer. It won't work for exponentiation tables of Zn when n is the product of two distinct odd primes where a more vertical approach is required.

    The first few tough primes are 5, 11, 59, 83, 107, 179, 227, 347

    Below is not a pretty demo of the algorithm from above where the need for a multidimensional array to hold the table becomes apparent:

    Enter a tough prime or a power of a tough prime: