I have a number n from 2 to around 1e9 and I need to find the primitive root of n that's closest to n/φ. For instance, if n=89, the primitive root I want is 56. 54 is also a primitive root, but 89/φ is just greater than 55.
If n has no primitive roots, I want a number of the greatest multiplicative order.
Is it possible to compute this faster than O(n) on average? If some freak of a number has no primitive roots near n/φ, it's OK to take longer for that number.
I'm writing the program in Rust and Haskell, but C++ is fine as I've also been coding in that, or pseudocode.
A simple an efficient algorithm to find the element of maximum order in the group of units modulo m closest to m/φ is this:
Determine the maximum order in the group of units modulo m, given by the Carmichael function λ(m). This requires computing the prime factorization of m.
Compute the prime factorization of λ(m).
Construct the sequence of numbers closest to m/φ. Start with m/φ rounded to the next integer, then take the next closest number and so on.
Test whether any of the numbers has order λ(m). The first one that has is the number we are looking for.
By definition of the Carmichael function, we know that a^λ(m) = 1 for all λ. If a does not have maximum order, we must have a^(λ(m)/p) = 1 for some prime p dividing λ(m). If a^(λ(m)/p) ≠ 1 for all p|λ(m), a must have maximum order.
This check is relatively cheap. On average, we only need to check a handful of numbers before finding one of maximum order, even for moduli in the order of magnitude of 1e9. I benchmarked a mildly optimized Rust implementation of this algorithm on my machine. For odd moduli m, the code spends 60% of its time on the prime factorizations of m and λ(m), for even moduli about 40% of its time. For odd moduli it takes on average 4µs for each number, and that time hardly increases as m grows.