6.1.15

Life of Phi

In last years' Finding Phi post I presented an algorithm for finding the order of 2 mod n.

It is not a particularly fast one so I thought I'd modify it based on a few very basic observations about the structure of the row at 2 in exponentiation tables of Zn for n > 2 where n is the product of two distinct primes greater than 2:

  1. The row at 2 is a sequence  21 , 22 , 23 ,..., 2i  where every subsequent entry < n is equal to the previous one times 2, or in other words:
  2. a1 = 21 = 2
    a2 = 22 = 4
    a3 = 23 = 8
    .
    .
    .
    ai = ai-1 + ai-1
  3. At any index if ai > n then ai = n - ai

This is easy to see. And here's the algorithm in Javascript.


/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find the order of 2 mod n for n = p*q where p,q > 2  
 ---------------------------------------------------- */  
function findO2(n)
{
var a = 2;
var i = 1;
while(a !== 1)
{
   a = a + a;
   i = i + 1;
   if (a > n){ a = a - n;}   
} 
return i;
}


Since φ(n) / 2 is a universal exponent when n is the product of two distinct odd primes, then the above while loop will loop at most φ(n) / 2 times for any n that is the product of two distinct odd primes.

Example 1: Let n = 8767703359  where n = p*q and  p = 137483, q = 63773.  Since φ(n) = (p-1)(q-1) = (137483 - 1)(63773 - 1) = 8767502104, therefore φ(n) / 2 = 4383751052, which in this case is the smallest integer i such that 2i = 1 mod n. In other words, i = φ(n) / 2 = 4383751052 is the order of 2 mod 8767703359 because 24383751052 = 1 mod 8767703359.

The above algorithm produces this result  (after only a few "unresponsive script" nudges in the ribs), which is quite remarkable considering the fact that 24383751052 chokes the all mighty Windows Scientific Calculator and causes it to return Invalid Input right away.

Also, the above algorithm does not use modular arithmetic, or exponentiation in any way to find the order i of 2 mod n, which is the smallest integer such that  2i  = 1 mod n for n = p*q where p,q > 2.  

Here is the algorithm still in Javascript but with a webworker so no nudges in the ribs are required: