5.2.15

Finding Phi Faster

In here I laid out an algorithm for finding phi of n, or φ(n),  when n is the product of two distinct odd primes but the algorithm entailed a lot of exponentiation and modular arithmetic, which plays well with small exponents but chokes on even a 4 digit n.

On the other hand, in this post I outlined a simple algorithm for finding the order of 2 mod n when n is the product of two distinct odd primes.

This simple algorithm is crucial in finding φ(n) because the order of 2 mod n is the smallest integer k such that

2k = 1 mod n

Furthermore, since k divides φ(n) then the following brand new algorithm can get to phi of n without modulus, and without exponentiation simply by generating the row at 2 up to k as described and cycling through that row until n is reached as follows:

/* -------------------------------------------------
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
and use the order of 2 mod n to find phi(n)
---------------------------------------------------- */
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;
}

function find_phi(n)
{
var cycle_length = findO2(n);
var phi_length = 0;
while(phi_length < n)
{
phi_length =  phi_length + cycle_length;
}
return phi_length - cycle_length;
}

The worst case scenario for find_phi(n) is the best case scenario for findO2(n) - it is when the order of 2 mod n is either of the form r where r = (p-1)/2 and p is one of the primes, of which n is composed as described in Types of Exponents.

Below is a quite leaky implementation of the algorithm in Javascript using a single webworker.

Note that this is a Javascript implementation and it is quite leaky but nevertheless it can handle up to a 10 digit n in less than 35 minutes, which is still quite impractical in the real world of really large n.

Note: The implementation works when n is the product of any two distinct odd primes: safe primes, strong primes, sexy primes, you name it.