_{n}where n is the product of two distinct odd primes p and q and of Z

_{p}when p is a prime.

Another interesting type of exponentiation tables is that of Z

_{pk}when p is prime and k is any integer. If p is prime then p

^{k}has a primitive root so the only universal exponent mod p

^{k}is strictly φ(p

^{k}). In this case this is equal to:

φ(p

^{k}) = p^{k}− p^{k−1}= p^{k−1}(p − 1)Additionally, Z

_{pk}has elements i, j > 0 such that i

^{j}= 0 when i is any multiple of p. Therefore the rows i of the exponentiation table of Z

_{pk}that are multiples of p are simply 0 for j > 1

Below is the exponentiation table of Z

_{25}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 p

^{k}is φ(p

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

- Given an odd integer n list all even integers smaller than n,

followed by all odd integers smaller than n.

- 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:

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 Z

_{p}when p is a tough prime and Z

_{pk}when p is a tough prime and k is any integer.

__It won't work__for exponentiation tables of Z

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