Möbius function help

Question

Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate mobius(k). I saw some formula that had to do with primitive roots to calculate mobius(k), but I don't understand why it works nor how or how much faster it is, then say trying to factor the integer k.

Answer 1

I think the formula you're looking for involves Ramanujan sums, where $$c_q(n)= \sum_{a=1}_{(a,q)=1}^{q}e^{2\pi i\frac{a}{q}n} = \mu(n)$$ if $(n,q)=1$, where $\mu(n)$ is your Möbius function. I actually saw this today and was thinking the same thing; it's an interesting result, but is it any faster for primality testing? I don't know, we're looking at things of this form to get a hold on Goldbach's conjecture. Should be a comment, but there was no way the sum term would be readable in comment-form.

Answer 2

My understanding is that no one knows a way to calculate $\mu(n)$ guaranteed to be significantly faster than fully factoring $n$ into primes. Determining primality is much faster than factoring, hence, faster than computing $\mu$.