## 21.4.16

### Generating powers of k mod n

Previously I showed an algorithm for generating powers of 2 mod n without using multiplication or exponentiation. The algorithm can easily be modified to generate powers of any integer k mod n where the greatest common divisor of k and n is equal to 1.

The first part of the algorithm for generating powers of 2 mod n  required listing all even integers smaller than n followed by all odd integers smaller than n, which is simply the 2nd row of the multiplication table of Zn since each entry at this row and a column j > 0  is equal to 2+aj mod n and if GCD(2, n) = 1 then there exists an integer k < n such that 2*k = 1 mod n

For example, below are a few multiplication tables of Zn for n = 5, 7, 11: Each entry aij = i * j mod n

Note that in general for an entry aij at row i and column j, if aij == (n-i), then the end of the ith row has been reached and also if i+ aij-1> n then  aij = (i+aij-1) - n

For example, below is the multiplication table of Zn for n = 35;
Let i = 3. Each entry aj at the 3rd row is generated as aj = 3 + aj-1 while aj is not equal to (35-3) since 32 is the last entry of the 3rd row. Furthermore, if  (3 + aj-1) > 35 then aj = (3 + aj-1) - 35

The other function of the algorithm for generating powers of 2 mod n was the following. Given an array of the  ith row of the multiplication table:

a. Look up the value at initial index;
b. Make that value the initial index;
c. Save and Repeat a and b until the value equals 1

This function can be applied in general for generating powers of any k mod n as long as GCD(k,n) = 1

With this in mind the generalized algorithm for generating powers of k mod n where GCD(k,n) = 1
becomes:

``````/* -------------------------------------------------
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 k mod n,
generate the unique portion of row at k
of the exponentiation table of Z sub n
---------------------------------------------------- */

function powers_of_k_mod(n,k)
{
var index = 0;
var perm_slot = k;
var count = 1;
var perm = new Array(); var powers = new Array();
perm = generate_permutation(n, k);
powers.push(1);
powers.push(perm_slot);
while(perm_slot != 1)
{
index = perm_slot;
perm_slot = perm[index];
powers.push(perm_slot);
}
return powers;
}

/* -----------------------------------------------
generate kth row of the multiplication table
of Z sub n
-------------------------------------------------- */
function generate_permutation(n, k)
{
var index = 0;
var permutation = new Array();
permutation.push(0);
while(index!=(n-k))
{
index = index + k;
if (index > n) {
index = index - n;
}
permutation.push(index);
}
return permutation;
}
``````

Here's a point and click implementation of the algorithm above.