31.8.15

The Art Of Overcounting

The function find_phi(n) pops up in almost all of my algorithms for finding phi of n, and almost always I point out that it is a function that may overcount.

Here's what I mean by that: if the order k of an element a mod n is less than the difference between n and phi(n) then the result from find_phi(n) will be a higher multiple of k than phi(n). In other words:

If k < (n - phi(n)) where ak = 1 mod n and k is the smallest such integer for a, then find_phi(n) returns  r such that r > phi(n) and (r-k)= phi(n)

Example:  Let p = 7 and q = 13 then n = p*q = 91 and let a = 2. Since n is the product of 2 distinct odd primes, then any of my functions for finding the order of 2 mod n described in Generating Exponentiation Tables and Phi Not Pi (neither of which uses exponentiation) will return k = 12
Since phi(n) = (p-1)(q-1) then in this case phi(91) = 72 but find_phi(91) returns 84 so r = 84, and as predicted (r-k) = 84 - 12 = 72 = phi(n)

In such a case where the order k of an element a mod n is less than the difference between n and phi(n) some manual poking will be required to retrieve phi(n) using find_phi(n), namely the order of 2 mod n must be returned along with the result of find_phi(n) so that it can be subtracted until phi(n) is reached but there are other functions for finding phi of n once the order of a particular element is known.

The most crucial piece of the puzzle in finding phi(n) is finding the order of an element mod n fast enough where "fast enough" is a relative concept.