How to factor numbers that are the product of two primes

What are techniques to factor numbers that are the product of two prime numbers? For example, how would we factor $262417$ to get $397\cdot 661$? Would we have to guess that factorization or is there an easier way?

Solution 1:

The problem of the factorization is the main property of some cryptograpic systems as RSA.

This fact has been studied for years and nowadays we don't know an algorithm to factorize a big arbitrary number efficiently.

However, if $p*q$ satisfies some propierties (e.g $p-1$ or $q-1$ have a soft factorization (that means the number factorizes in primes $p$ such that $p \leq \sqrt{n}$)), you can factorize the number in a computational time of $O(log(n))$ (or another low comptutational time)

If you are interested in it, you can check this pdf with some famous attacks to the security of RSA related with the fact of factorization of large numbers.

http://www.nku.edu/~christensen/Mathematical%20attack%20on%20RSA.pdf

Solution 2:

At the risk of being a necromancer ...

... factorising a number we know to be the product of two primes should be easier than factorising a number where we don't know that.

Has anyone done an attack based on working backwards through the number?

For example, as we know 262417 is the product of two primes, then these primes must end with 1,7 or 3,9. Our solution is therefore abcde1 x fghij7 or klmno3 x pqrst9 where the letters need to be determined.

Now work with the last pair of digits in each potential solution (e1 x j7 and o3 x t9) and eliminate all those digits for e, j, o and t which do not produce a 1 as the fifth digit. We have the complication of dealing with possible carries.

Obviously the tree will expand rather quickly until it begins to contract again when investigating the frontmost digits.