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.