Algorithms

Generating powers of k mod n

The following is an algorithm for the case when GCD(k,n) = 1. Here is the algorithm for all cases.

1. List the kth row of the multiplication table of Z_n: for an entry a_ij at row i and column j of the multiplication table of Z_n,  if a_ij == (n-i) then the end of the i^th row has been reached and also if i+ a_ij-1> n then  a_ij = (i+a_ij-1) - n
2. 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 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 where GCD(k,n) = 1, 
 generate the unique portion of row at k
 of the multiplication 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;
}

For the case of when k = 2 I have several different variations of this algorithm.

I first described the most basic one in a post titled Phi Not Pi, but here's a better explanation of it.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all powers of 2 mod n, 
 generate the unique portion of row at 2
 of the exponentiation table of Z sub n
 ---------------------------------------------------- */  

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);
 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;
}

Moving onto a fancier variation, which takes into account the fact that the (n+1)/2 row of the exponentiation table mod n is equivalent to the 2 row of the exponentiation table mod n

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all powers of 2 and (n+1)/2 mod n 
 ---------------------------------------------------- */  
//generate powers of 2 from highest to lowest exponent
function powers_of_two_backwards(n)
{
 var index = 0;
 var perm_slot =1;
 
 var perm = new Array(); var powers = new Array();
 perm = generate_faster_permutation(n);
 do{
    index = perm_slot;
    perm_slot = perm[index];
    powers.push(perm_slot); 
   }while(perm_slot != 1)
 return powers;
}
//generate row at (n+1)/2  of the multiplication table 
function generate_faster_permutation(n)
{ 
 var start = (n+1)/2;
 var end = (n-1)/2;
 var perm = new Array();
 perm.push(0);perm.push(start);
 for(i=1; i<=end; i++)
 {
     perm.push(i);
     start = start+1;
     perm.push(start);
 }
 perm.pop();  
 return perm; 
}

So far all of these algorithms require the generation of a row of the multiplication table mod n but the one algorithm below does not. It is also slightly reminiscent of the algorithm behind the Collatz conjecture and again, it doesn't require modular arithmetc.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all powers of 2 and (n+1)/2 mod n 
 ---------------------------------------------------- */  
//generate powers of 2 from highest to lowest exponent
function powers_of_two_backwards_again(n)
{
 var k = (n+1)/2;
 var halfie = k;
 var powers = new Array();
 do{
    powers.push(k); 
    if (k%2 == 0)
    {k = k/2;}
    else
    {k = ((k-1)/2)+halfie;}
   }while(k != 1)
 return powers;
}

Generating Multiplication Tables

1. (Generate a subset with starting index k_{i ,}while starting index k_i is less than or equal to n-1 shift it by k, add that subset to a table T, (return T if it reached the n*((n-1)/2)th index)
2. If the last index of that subset is equal to  n - ( k - 1 ) then go to (1.) with  k_i = 1, k = k, and table T; 
3. Else if the last index of that subset is equal to n - k then go to (1.) with k_i = 0, k = k+1, and table T; 
4. Else if the last index of that subset is less than n and the row k is less than n/2 then shift  new_k_i = k-(n - k_i) and go to (1.) with k_i = new_k_i ,  k = k, and table T;
5. Return table T;

//Author: Marina Ibrishimova
//Purpose: Generate the first half of the multiplication table of Zn 
//without actually computing the GCD(each_row_index*each_column_index, n)
function StopHammerTime(ki, k, n, table_so_far) {  
  var len = table_so_far.length;  
  var half_table_slots = n*((n-1)/2);  
  if(len == half_table_slots) {return;}  
  else {   
   while ( ki <= (n - 1)) {  
   table_so_far.push(ki);  
   ki = ki + k;  
   }  
   len = table_so_far.length;  
   var last_inset = table_so_far[len-1];  
   var k_dist = n - last_inset;   
   var new_ki = k - k_dist;   
   var n_k = k + 1;  
   if(last_inset == n-(k-1) && k < n/2) { StopHammerTime(1, k, n, table_so_far); }  
   else if(last_inset == n-k && k < n/2) { StopHammerTime(0, n_k , n, table_so_far); }  
   else if(last_inset < n && k < n/2){ StopHammerTime(new_ki, k, n, table_so_far); }  
   }  
   return table_so_far;    
 }