## 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;
}
``````