24.4.16

Generating powers of powers of k mod n

Previously I showed how to generate an array of powers of k mod n by cycling through the kth row of the multiplication table of Zn .

Powers of powers of k mod n, or powers of each entry in the powers of k mod n array can also be generated without using multiplication or exponentiation by cycling through the array since by construction the array of powers of k mod n is the unique portion of the kth row of the exponentiation table of Zn   

Claim: Given the unique portion of the kth row of the exponentiation table of Zn, namely: k0,k1,k2,k3, ..., kwhere r is the smallest integer for which k is equal to 1 mod n, then all powers of powers of k mod n for all k and n such that GCD(n,k) = 1, namely k21, k22, k23,..., k2r2, k32, k33, k34,..., k3r3,...  are elements of the kth row of the exponentiation table of Zsuch that the powers of each element at index i are at a distance of i from each other within the row.

Proof: Coming soon.

Example: Let n = 35 and k = 2
The unique portion of the 2nd non-zero row of the exponentiation table of Z35 is:

k0,k1,k2,k3, ..., k12  = 1,2,4,8,16,32,29,23,11,22,9,18,1

The powers of powers of 2 mod 35 are
k21, k22, k23,..., k2r1=  4,16,29,11,9,1
k31, k32, k33, k3r2 = 8,29,22,1
k41, k42, k4r3 = 16,11,1
k51, k52, k53,..., k5r4 = 32,9,8,11,2,29,18,16,22,4,23,1
k61, k6r5 = 29, 1
k71, k72, k73,..., k7r6 = 23,4,22,16,18,29,2,11,8,9,32,1
k81, k82,  k8r7 = 11,16,1
k91, k92, k93,..., k9r8 = 22,29,8,1
k101, k102, k103,..., k10r9  = 9,11,29,16,4,1
k111, k112, k113,..., k11r9  = 18,9,22,11,23,29,32,16,8,4,2,1


where r1, r2, r3,... are the orders of k2 mod n, k3 mod n, k4 mod n, and so on or in other words,  k2r1 = 1 mod n,  k3r2= 1 mod n,  k4r3 = 1 mod n, and r1, r2, r3, .... are the smallest integers for which the power of power of k equals 1.



In the 2nd non-zero row of the exponentiation table  k2 =  k21 = 4 and k2 is 2 slots away from k1 ; k22 is 16 and it is 2 slots away from k2,  k2is also  2 slots away from k22, and so on until k2r2is reached, which has a value of 1. Similarly, k31 = 8, which is 3 slots away from k1; k3 is 3 slots away from k31, and so on for all powers of powers of k.

The following function can then be used to generate all powers of powers of k mod n, given the output from the algorithm for generating powers of k mod n presented here where the variable cycle refers to that output array, index is the current index within that array, length is the length of the array, and table contains all powers of powers generated.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Generate powers of powers of k mod n, 
 generate the unique portion of row at k, and rows
 at powers of k of the exponentiation table of Zn
 ---------------------------------------------------- */  
// a.Look up the value at initial index of cycle/powers.
// b.Make that value the initial index of cycle/powers.   
// c.Save and repeat until the cycle's current value equals 1. 
function generate_powers_of_powers(cycle, index, len, table)
{
var temp = index;
var k = cycle[index];
table.push(k);
  while(k != 1) {
  temp = temp + index;
  if (temp > len){temp = temp - len;}
  k = cycle[temp];
  table.push(k);
 }
 if(cycle[index+1] != 1)
 {
  index = index + 1;
  generate_powers_of_powers(cycle, index, len, table)  
 }
return table;
}


I added this function to a new version of the powers of k mod n algorithm.