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.
Möbius function help
1
$\begingroup$
number-theory
functions
computational-complexity
2 Answers
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.
-
0It cannot be faster than primality testing in the case where $n$ is suspected to be either prime or the product of two primes, can it? – 2012-11-23
-
0Clearly if $n$ is suspected to be either prime of the product of two primes than the Mobius function would be able to determine primality of $n$.. and this looks like a pretty fast way to calculate $\mu$ – 2012-11-23
-
1Something seriously wrong here. If $n$ is odd, you can take $q=2$, and the formula says $\mu(n)=e^{\pi in}=-1$. Please check your source. – 2012-11-23
-
0Ya I see that. Hmm, seems the way I wrote it in my notes.. I'll need to check with others in the course – 2012-11-23
-
0@GerryMyerson it should be the sum of the primitive nth roots of unity $\mu(n)=\sum_{k}e^{2\pi i k/n}$, where k ranges over the integers coprime to n – 2013-03-28
1
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$.