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: