20.5.15

Phi Not Pi

I came up with another way of finding the order of 2 mod n without doing exponentiation mod n and without using the way already described in Life of Phi

This new trick is slower than the one described in Life of Phi but faster than plain exponentiation, and it is based on a cyclic permutation and the following claim:

Claim: The length of the first cycle in a permutation f of length n when n is the product of two distinct odd primes is the order of 2 mod n.

Here's (not the most efficient yet working) implementation of the claim above 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 order_of_two_mod(n)
{
 var index = 0;
 var perm_slot = 2;
 var count = 1;
 var perm = new Array();
 perm = generate_permutation(n);
 while(perm_slot != 1)
 {
    index = perm_slot;
    perm_slot = perm[index];
    count = count + 1;
 }
 return count;
}

//generates the second 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.




Example: n = 242710681
The algorithm described in this post here returns 4044300 in 6.9 minutes.
The algorithm described in the first Life of Phi returns 4044300 in 2 second

Once again, below is a JS implementation of the algorithm described in the first Life of Phi post




Note: Once again, the algorithm described in this post is slower than the algorithm described in the first Life of Phi post, but it is nevertheless interesting.

Theoretically, if the permutation already exists stored somewhere as opposed to generating it on the fly, then order_of_two_mod(n) will also only loop at most φ(n)/2 times just like the function findO2(n), which was described in Life of Phi.

In other words, given n that is the product of two distinct odd primes p and q, then less than half of n is the worst case for both findO2(n) and order_of_two_mod(n) (if order_of_two_mod(n)'s permutation is pre existing somewhere) since by definition of Euler's Totient Function φ(n) is equal to the number of integers coprime with n, which is (p-1)(q-1).

p.s. Several people have warned me to drop this problem from the list of problems that I'm interested in because it is a dangerous problem to work on. However,  the fact that my blog is less popular than say a blog with female soft porn encourages me to dig even deeper into this problem.