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.
$\begingroup$
$\endgroup$
asked Nov 23, 2012 at 4:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ It 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? $\endgroup$ Nov 23, 2012 at 6:53
-
$\begingroup$ Clearly 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$ $\endgroup$– user45793Nov 23, 2012 at 7:04
-
1$\begingroup$ Something 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. $\endgroup$ Nov 23, 2012 at 11:49
-
$\begingroup$ Ya I see that. Hmm, seems the way I wrote it in my notes.. I'll need to check with others in the course $\endgroup$– user45793Nov 23, 2012 at 15:57
-
$\begingroup$ @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 $\endgroup$ Mar 28, 2013 at 5:45
$\begingroup$
$\endgroup$
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$.
answered Nov 23, 2012 at 4:43