7.3.16

Generating Powers of 2 mod n

In "Lonely Squares" I showed an algorithm for generating all unique powers of 2 mod n when n is the product of two distinct primes p, q (in that example I used p = 3 and q = 7 to illustrate it)

I also used this picturesque graph to illustrate it

Note: n can be any odd integer, not just a product of two distinct primes.

In general, the "Lonely Squares" algorithm can be summed up in two simple functions that do not require exponentiation to generate [21, 22, 23,..., 2k]  where k is the smallest integer such that 2k = 1 mod n, or in other words k is the order of 2 mod n and n is any odd integer.

  1. Given an odd integer n list all even integers smaller than n, 
    followed by all odd integers smaller than 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.  

I first showed a version of this algorithm here but I presented it as a finder of the order of 2 mod n. However, as it can be seen here, it is very easy to modify it to list all powers of 2 mod n up to k where k is the order of 2 mod n.

Below is a Javascript implementation although a lower level language might be more appropriate:


/* -------------------------------------------------  
 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;
}


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