Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question

2 Answers

up vote 1 down vote accepted

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 Mobius 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.

share|improve this answer
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? – Hagen von Eitzen Nov 23 '12 at 6:53
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$ – user45793 Nov 23 '12 at 7:04
1  
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. – Gerry Myerson Nov 23 '12 at 11:49
Ya I see that. Hmm, seems the way I wrote it in my notes.. I'll need to check with others in the course – user45793 Nov 23 '12 at 15:57
@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 – Ethan Mar 28 at 5:45
up vote 1 down vote

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.