8.8.15

Optimizing Life Of Phi Function

In Life of Phi I wrote a function for finding the order of 2 mod n when n is the product of two distinct odd primes then I uncovered a faster way of doing this here, and a couple of slower ones described here, and here.

Using Javascript's remainder operator, which does not act as a modulus operator unless all expressions and values involved are always positive, I can speed up the function findO2(n) described in Life of Phi because the expression (a + a) is always positive given a positive starting a.

Below is the optimized version of findO2(n), which finds the order of 2 mod n in approximately the same amount of time as find_order(n) described in Generating Exponentiation Tables (or slightly faster).

/* -------------------------------------------------  
 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 | p,q > 2 
 ---------------------------------------------------- */ 

function findoO2(n)
{
var a = 2;
var i = 1;
while(a != 1)
{
   a = (a + a)%n;
   i = i + 1; 
} 
return i;
}