Take the 2-minute tour ×

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 1

up vote 2 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
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


