_{n }.

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 Z

_{n}

**Claim:**Given the unique portion of the kth row of the exponentiation table of Z

_{n}, namely: k

^{0},k

^{1},k

^{2},k

^{3}, ..., k

^{r }where r is the smallest integer for which k

^{r }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 k

^{21}, k

^{22}, k

^{23},..., k

^{2r2}, k

^{32}, k

^{33}, k

^{34},..., k

^{3r3},... are elements of the kth row of the exponentiation table of Z

_{n }such 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 Z

_{35}is:

k

^{0},k

^{1},k

^{2},k

^{3}, ..., k

^{12 }= 1,2,4,8,16,32,29,23,11,22,9,18,1

The powers of powers of 2 mod 35 are

k

^{21}, k

^{22}, k

^{23},..., k

^{2r1}= 4,16,29,11,9,1

k

^{31}, k

^{32}, k

^{33}, k

^{3r2}= 8,29,22,1

k

^{41}, k

^{42}, k

^{4r3}= 16,11,1

k

^{51}, k

^{52}, k

^{53},..., k

^{5r4 }= 32,9,8,11,2,29,18,16,22,4,23,1

k

^{61}, k

^{6r5 }= 29, 1

k

^{71}, k

^{72}, k

^{73},..., k

^{7r6 }= 23,4,22,16,18,29,2,11,8,9,32,1

k

^{81}, k

^{82}, k

^{8r7 }= 11,16,1

k

^{91}, k

^{92}, k

^{93},..., k

^{9r8 }= 22,29,8,1

k

^{101}, k

^{102}, k

^{103},..., k

^{10r9 }

^{ }= 9,11,29,16,4,1

k

^{111}, k

^{112}, k

^{113},..., k

^{11r9 }

^{ }= 18,9,22,11,23,29,32,16,8,4,2,1

where r1, r2, r3,... are the orders of k

^{2}mod n, k

^{3}mod n, k

^{4}mod n, and so on or in other words, k

^{2r1}= 1 mod n, k

^{3r2}= 1 mod n, k

^{4r3}= 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 k

^{2}= k

^{21 }= 4 and k

^{2}is 2 slots away from k

^{1 }; k

^{22}is 16 and it is 2 slots away from k

^{2}, k

^{23 }is also 2 slots away from k

^{22}, and so on until k

^{2r2}is reached, which has a value of 1. Similarly, k

^{31}= 8, which is 3 slots away from k

^{1}; k

^{32 }is 3 slots away from k

^{31}, 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 Z
```_{n}
---------------------------------------------------- */
// 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.