1
$\begingroup$

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

  • 0
    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)$.2012-03-06
  • 0
    @WNY but this would oppose Gerry's answer because ["PRIMES is in P"](http://www.google.de/url?sa=t&rct=j&q=%22Primes+is+in+P%22&source=web&cd=1&ved=0CCsQFjAA&url=http%3A%2F%2Fwww.cse.iitk.ac.in%2Fusers%2Fmanindra%2Falgebra%2Fprimality_v6.pdf&ei=APlVT74FxJSzBvjq6e0G&usg=AFQjCNGvhedNI0NYO2ALeuGmJANPqp5WlQ) (link to the pdf)2012-03-06
  • 0
    @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).2012-03-08

1 Answers 1

2

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

  • 0
    Solvable in linear time on a quantum computer, you mean?2012-03-06
  • 0
    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.2012-03-06
  • 0
    Could reply to @WNY 's [comment](http://math.stackexchange.com/questions/117034/multiplicity-of-factors-without-acutal-factoring#comment271987_117034)?2012-03-08
  • 1
    The references cited in http://mathforum.org/kb/message.jspa?messageID=379888&tstart=0 may be useful. There's also a reference at http://mathforum.org/kb/message.jspa?messageID=379871&tstart=0.2012-03-08