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

  • 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