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.

Highest Order

Definition: The highest order of an element mod n is the order k of any element(s) such that k is equal to the least universal exponent mod n.

Note: least universal exponent as defined on page 268 in Rosen, K. Number Theory And Its Applications, 2005

Example: Given a pair of odd primes (p = a1*r + 1, q = a2*s + 1), then the highest order mod p*q is phi(p*q)/GCD(a1, a2)

Example: Given an odd prime p then the highest order is phi(p), same goes for a power of a prime, or 2 times any prime or 2 times any power of a prime.

Example: In here I conjectured that if p and q are safe primes (ie primes of the form 2s+1 where s is also a prime) such that at least one of p, q is not congruent to -1 mod 8 (I called these tough primes) then 2 mod p*q is phi(p*q)/2 which is the highest order possible mod p*q

Conjecture: Given an odd prime p then 2 mod p is of highest order if p is a tough prime.

Conjecture: Given a power of an odd prime p^t then 2 mod p^t  is of highest order if p is a tough prime.