Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
mersenne.org/various/math.php (about Mersenne's primes) –  Dunno Jan 30 at 15:08
    
For very small numbers, trial division actually is the best method. –  Peter Jan 30 at 15:10
    
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. –  Peter Jan 30 at 15:11
    
Simply google for prime factorization to get a survey. –  Peter Jan 30 at 15:12
    
Using all known methods a 100-digit-number can be factored in about one day! –  Peter Jan 30 at 15:14
show 1 more comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
1  
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. –  Greg Martin Jan 30 at 16:21
    
Yes, I was referring to the general task, not the specific method suggested, that wasb't very clear indeed. –  fkraiem Jan 30 at 16:48
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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