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.

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

Generating Multiplication Tables

- (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) - 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; - 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; - 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; - Return table T;

```
//Author: Marina Ibrishimova
//Purpose: Generate the first half of the multiplication table of Z
```_{n}
//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;
}