30.7.16

Generating multiples of k mod n

In my previous post I showed how one row of the multiplication table of Zn when n is the product of distinct odd primes can be generated using less iterations than others. 

My function for generating multiples of an arbitrary k will always make n-1 iterations to get to the n-k element, which is the last element in the kth  row of the multiplication table of Zn 


However, as I showed in my previous post, if k = (n+1)/2 then the kth  row of the multiplication table of Zn  has the following pattern [k, 1, k+1, 2, k+2, 3, k+3,..., n-1, n-k],
which can be produced in half the number of iterations needed in an additive function for an arbitrary k which takes n-1 iterations.

Also ((n+1)/2)*2 = n+1 = 1 mod n because n = 0 mod n and 2 = ((n+1/2))r-1 where r is the order of (n+1)/2

Similarly, 
((n+1/2))2 * 22 = 1 mod n and 22 = ((n+1/2))r-2 mod n 
((n+1/2))3 * 23= 1 mod n  and 2=((n+1/2))r-3
((n+1/2))4 * 2= 1 mod n and 24 = ((n+1/2))r-4 mod n 
.
.
.
and so on until a lonely square is reached.

In general I claim that:


Claim: If n is the product of distinct primes and k and r are integers such that kr= k mod n and r is the smallest such integer then for all i such that 1< i < r 

ki * kr-1-i = 1 mod n        | if GCD(k,n) = 1
ki * kr-i = k mod n           | if GCD(k,n) > 1

When k = (n+1)/2, every second integer in the kth  row of the multiplication table of Zn (in other words the array of multiples of k) is just the index of the previous integer starting from an initial k, which is then gradually increased by 1, forming the following sequence [k, 1, k+1, 2, k+2, 3, k+3,..., n-1, n-k]



When k = ((n+1)/2)2 mod n, every fourth integer in the array of multiples of k is the index of the block of the previous 3 integers starting from k, k+k, k+k+k, which are then gradually increased by 1, forming the following sequence [k,  k+k,  k+k+k, 1,  k+1, k+k+1, k+k+k+1, 2,..., n-1, n-k]

With this in mind and the observations I made here, if k = ((n+1)/2)2 mod n then all multiples of k can be generated in 1/4 of the number of iterations needed for an arbitrary k although the total number of  inserts into the array of multiples remains the same.

I just need to initialize the first 3 values and calculate the actual number of iterations, which is the floor of (n-1)/4, and then iterate n/4 times while inserting 4 values into the array at each iteration because apparently I'm not satisfied with just inserting only 2   values at the same time.

Similarly, if k = ((n+1)/2)3 mod n then all multiples of k can be generated in 1/8 of the number of iterations needed for an arbitrary k and so on although the total number of inserts into the array of multiples remains the same.


Here's the implementation for k = ((n+1)/2)2 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 multiples of ((n+1)/2)^2 mod n 
 ---------------------------------------------------- */ 

function generate_multiples(n)
{ 
 var k_one = (((n-1)/2)*((n-1)/2))%n;
 var k_two = (k_one+k_one)%n;
 var k_thre = (k_two+k_one)%n;
 var end = Math.floor(n/4);
 var perm = new Array();
 perm.push(0);perm.push(k_one);
 perm.push(k_two);perm.push(k_thre);
 
 for(i=1; i<=end; i++)
 {
     perm.push(i);
     k_one = k_one+1;
     perm.push(k_one);
     k_two = k_two+1;
     perm.push(k_two);
     k_thre = k_thre+1;
     perm.push(k_thre);
 }  
 return perm; 
} 
 

This array of multiples may end up with up to 3 additional values but this will not affect the generic function for generating powers of k mod n that simply permutes through the array of multiples of k 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 multiples of ((n+1)/2)^2 mod n
and use that array to generate all powers of
 ((n+1)/2)^2 mod n, which are all powers of 4 mod n 
in reverse order
 ---------------------------------------------------- */ 

function generate_multiples(n)
{ 
 var k_one = (((n-1)/2)*((n-1)/2))%n;
 var k_two = (k_one+k_one)%n;
 var k_thre = (k_two+k_one)%n;
 var end = Math.floor(n/4);
 var perm = new Array();
 perm.push(0);perm.push(k_one);
 perm.push(k_two);perm.push(k_thre);
 for(i=1; i<=end; i++)
 {
     perm.push(i);
     k_one = k_one+1;
     perm.push(k_one);
     k_two = k_two+1;
     perm.push(k_two);
     k_thre = k_thre+1;
     perm.push(k_thre);
 }  
 return perm; 
} 

function generate_powers(n)
{
 var index = 0;
 var perm_slot =1;
 var perm = new Array(); var powers = new Array();
 perm = generate_multiples(n);
 do{
    index = perm_slot;
    perm_slot = perm[index];
//the order of k mod n can also be found 
//through counting the # of iterations
    powers.push(perm_slot); 
   }while(perm_slot != 1)
 return powers;
}