## 25.7.15

### Finding Phi Even Faster

Renote: phi(n) is the number of integers that are coprime with n; phi(n) = (p-1)(q-1) when n is the product of two distinct odd primes p and q. In Types of Exponents I showed that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes.

In Life of Phi I came up with one way of finding the order of 2 mod n when n is the product of two distinct odd primes, and then I used it in Finding Phi Faster to find phi(n).

A few days ago I uncovered a new way of finding the order of 2 mod n when n is the product of two distinct odd primes.

This means that there's yet another way of finding phi(n) that is even faster than the way described in
Finding Phi Faster using the new algorithm described in Generating Exponentiation Tables.

The algorithm below re-uses the same overcounting find_phi(n) function from Finding Phi Faster but the entire algorithm in this post finds phi(n) even faster because find_order(n) is faster than findO2(n).

``````/* -------------------------------------------------
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 it to find phi(n)
---------------------------------------------------- */

function find_order(n)
{
var a = 1;
var aa = 2;
var aaa = 4;
var index = 0;
var order = 2;
while(index != 1)
{
index = (a + aa + aaa + a) % n;
a = aa;
aa = aaa;
aaa = index;
order = order + 1;
}
return order;
}

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

Example: n = 8767703359 where n = p*q and p = 137483, q = 63773

Without worker.js the new algorithm finds phi(n) in less than 30 seconds whereas the old algorithm takes a couple of minutes.

With worker.js the new algorithm finds phi(n) in 18 : 58 whereas the old algorithm takes 25 : 7 !
Clearly worker.js is overworked and underpaid but that's not the point.

A few more examples below:

`n = 12899*11483 = 148119217`
`n = 17327*34703 = 601298881`
`n = 55103*42767 = 2356590001    `
`n = 83243*40127 = 3340291861  `
`n = 62303*164999 = 10279932697  `
`n = 547357*195971 = 107266098647  `
Below is an implementation of this new algorithm with worker.js followed by an implementation of the old algorithm with worker.js.

The algorithm described in this post with a worker:

The algorithm described in Finding Phi Faster with a worker:

## 23.7.15

### Generating Exponentiation Tables

I hinted at one way of generating exponentiation tables in the last post of the Life of Phi trilogy, which involved dealing with permutations but there's another interesting way of generating exponentiation tables that relies on the following observation:

Each entry aij in the exponentiation table with i rows and j columns  of Zn when n is the product of 2 distinct primes can be generated as follows:

aij = [(j - 1)(ai-1 + ai-2 + ai-3)] + ai-3  mod n

Below is an algorithm for finding the order of any element of the exponentiation table of Zn when n is the product of 2 distinct primes. It can easily be modified to generate the entire table recursively.

It's also fast.

``````/* -------------------------------------------------
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 any a mod n for n = p*q where p,q > 2
---------------------------------------------------- */

function find_order(n, a)
{
var anot = 1;
var aa = a;
var aaa = a*a;
var coef = a - 1;
var index = 0;
var order = 2;
var bingo = "a divides n";

while(index != 1)
{
if (index === a) {return bingo;}
index = (coef*(anot + aa + aaa) + anot) % n;
anot = aa;
aa = aaa;
aaa = index;
order = order + 1;
}
return order;
}

``````

Example: The algorithm described in this post here and implemented with a worker finds it in 1:49 min whereas the algorithm implemented in Life of Phi and featured in Finding Phi Faster finds the order of 2 mod 915313319 in 2:20 min. The worker slows things down a bit, like quite a bit.

The above algorithm returns the correct answer for the order of 2 mod 915313319 in less than 20 seconds and only one "unresponsive script" nudge in the ribs required to return the correct result! What's more impressive is that find_order(n, a) can find the order of any element a of Zn if GCD(a, n) = 1 or find a zero divisor of Zn , and in particular it can find the order of 4 mod n much faster.

Indeed, in a web console find_order(n, a) returns the order of 4 mod 915313319 in less than 10 seconds!