For prime factorization, is there another way of doing it, distinct from dividing the number by a series of primes (starting by the smallest)?

Couldn't we also pick the same series of primes and multiply them somehow until we got the target number?

It's clear that any approach will imply lots of computation, but some ways could be tougher than others, couldn't they?

Is there a name for an exploratory multiplication to try to reach a number?

I am specially interested in doing this with big numbers. It's clear that finding the prime factors of 24 or 32 is an easy task in both directions (dividing or multiplying). But with things like 598703019332, would it be feasible at all?

  • $\begingroup$ mersenne.org/various/math.php (about Mersenne's primes) $\endgroup$ – Dunno Jan 30 '14 at 15:08
  • $\begingroup$ For very small numbers, trial division actually is the best method. $\endgroup$ – Peter Jan 30 '14 at 15:10
  • $\begingroup$ For 20 digit-numbers it is already cumbersome, and for, lets say, 80-digit numbers, it is unfeasible. There are much better methods for such numbers. $\endgroup$ – Peter Jan 30 '14 at 15:11
  • $\begingroup$ Simply google for prime factorization to get a survey. $\endgroup$ – Peter Jan 30 '14 at 15:12
  • $\begingroup$ Using all known methods a 100-digit-number can be factored in about one day! $\endgroup$ – Peter Jan 30 '14 at 15:14

"Is there a name for an exploratory multiplication to try to reach a number?"

Yes, it is called integer factoring, and it has received a lot of attention since ancient times, but even more so in the last few decades since it has become of practical significance. Just Google it, you will find more information about it than you probably want.

  • 1
    $\begingroup$ To be clear, no reasonable method uses "exploratory multiplication" in the sense of trying to guess the factorization and then multiplying to see if it works. All factoring methods proceed by trying to find a nontrivial divisor of the original number. $\endgroup$ – Greg Martin Jan 30 '14 at 16:21
  • $\begingroup$ Yes, I was referring to the general task, not the specific method suggested, that wasb't very clear indeed. $\endgroup$ – fkraiem Jan 30 '14 at 16:48

An efficient implementation of this "exploratory multiplication" could be implemented via remainder trees, see [1]. This could actually be useful for some types of numbers up to about 20 digits, though for most numbers of that size ordinary techniques (trial division, SQUFOF, and rho) will be superior.

[1]: Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic Number Theory (2008), edited by Buhler and Stevenhagen, pp. 325–384.


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.