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 0 down vote favorite

Is there a way to get the multiplicity of all prime factors of a given composite number, without doing the actual factorisation?

For example $24$ would have multiplicities $(3,1)$, because of $24=2^33^1$.

share|improve this question
I may be a bit confused about the actual question, but shouldn't this problem be at least as hard as deciding whether the given number is a prime? Indeed, if $m(p) = (k_1,k_2,\dots,k_n)$ where $k_i$ are multiplicities, then $p$ is a prime if and only if $m(p) = (1)$. – William Mar 6 '12 at 11:27
@WNY but this would oppose Gerry's answer because "PRIMES is in P" (link to the pdf) – draks ... Mar 6 '12 at 11:50
@WNY, it certainly is at least as hard as deciding primality, but I think in fact it's much harder than that, and no easier than factorization (which is in practice, and one expects in theory, much harder than deciding primality). – Gerry Myerson Mar 8 '12 at 22:28

1 Answer

up vote 1 down vote accepted

It is believed that even deciding whether an integer is squarefree is as hard as factoring.

share|improve this answer
Solvable in linear time on a quantum computer, you mean? – draks ... Mar 6 '12 at 11:23
When I have a quantum computer on my desk, I'll worry about how hard it is to solve problems on a quantum computer. In the meantime, that's not the computation model I have in mind. – Gerry Myerson Mar 6 '12 at 11:47
Could reply to @WNY 's comment? – draks ... Mar 8 '12 at 20:53
1  
The references cited in mathforum.org/kb/message.jspa?messageID=379888&tstart=0 may be useful. There's also a reference at mathforum.org/kb/message.jspa?messageID=379871&tstart=0. – Gerry Myerson Mar 8 '12 at 22:47

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.