6
$\begingroup$

Consider the two numbers $N_1=p_1\cdot p_2$ and $N_2=p_1^2\cdot p_2$, where $p_1$ and $p_2$ are primes.

Is there any factoring algorithm that can factor $N_2$ faster than the asymptotically fastest currently known factoring algorithm could factor $N_1$; that is, is there some trick that can use the fact that $N_2$ contains a square factor to speed up factorization?

$\endgroup$
2
$\begingroup$

In short, no, there is no such known algorithm.

Checking, if a number is squarefree, is currently as hard as factoring.

For small numbers, you can gain time because you only need to check upto the third root of N instead of the square root of N.

But for large numbers, this method is still not feasible.

With ECM, you can rule out small factors with high probability.

But in general, there is no shortcut.

$\endgroup$
  • 1
    $\begingroup$ Note, that the situation is completely different with single-variate polynomials. Here, the derivate helps to find out very quickly, if they are squarefree. $\endgroup$ – Peter Feb 5 '14 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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